C++ solution DSU
Find components of graph after removing initial nodes. The for each initial node find all the components from the modified graph it can reach. Keep a count vari
Find components of graph after removing `initial` nodes. The for each initial node find all the `components` from the modified graph it can reach. Keep a `count` variable for the count of `inital` nodes from which we can reach this component from the modified graph. Now if we remove node `i` from `initial`, then all the component `j` which have `count[j] = 1` can be prevented from malware spread if we remove `i` from `initial`. The number of nodes that can be prevented from malware spread will be the size of the component `j`. Find such `i` from `initial` which can prevent highest number of malware spread nodes, and in case of tie, select the one with lower `i`.\n\nComplexity:\n=> DSU operations can be assumed to take `\u0398(1)` operations.\nTime => `O(N^2)`, where `N = number of nodes in graph`\nSpace => `O(N)`, where `N = number of nodes in graph`\n\n```\nclass DSU{\nprivate:\n    vector<int> _parent, _size;\npublic:\n    DSU(int n){\n        _parent.resize(n);\n        _size.resize(n, 1);\n        for(int i = 0; i < n; i++){\n            _parent[i] = i;\n        }\n    }\n    \n    int find(int i){\n        return _parent[i] == i ? i : _parent[i] = find(_parent[i]);\n    }\n    \n    int size(int i){\n        return _size[find(i)];\n    }\n    \n    bool doUnion(int i, int j){\n        int pi = find(i);\n        int pj = find(j);\n        if(pi != pj){\n            if(_size[pi] >= _size[pj]){\n                _parent[pj] = pi;\n                _size[pi] += _size[pj];\n            }\n            else{\n                _parent[pi] = pj;\n                _size[pj] += _size[pi];\n            }\n            return true;\n        }\n        return false;\n    }\n};\n\nclass Solution {\npublic:\n    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {\n        int n = graph.size();\n        DSU dsu(n);\n        vector<bool> isInitial(n, false);\n        for(auto i: initial){\n            isInitial[i] = true;\n        }\n        \n        for(int i = 0; i < n; i++){\n            if(isInitial[i])continue;\n            for(int j = 0; j < n; j++){\n                if(isInitial[j])continue;\n                if(graph[i][j])dsu.doUnion(i, j);\n            }\n        }\n        \n        vector<int> count(n, 0);\n        vector<set<int>> components(n);\n        for(auto i: initial){\n            for(int j = 0; j < n; j++){\n                if(isInitial[j])continue;\n                if(graph[i][j])components[i].insert(dsu.find(j));\n            }\n            for(auto j: components[i]){\n                count[j]++;\n            }\n        }\n        \n        int ans = initial.front(), score = 0;\n        for(auto i: initial){\n            int curr = 0;\n            for(auto j: components[i]){\n                curr += (count[j] == 1 ? dsu.size(j) : 0);\n            }\n            if(curr > score || (curr == score && i < ans)){\n                score = curr;\n                ans = i;\n            }\n        }\n        return ans;\n    }\n};\n```
[]