You are given a network of n nodes represented as an n x n adjacency matrix graph, where the ith node is directly connected to the jth node if graph[i][j] == 1.

Some nodes initial are initially infected by malware. Whenever two nodes are directly connected, and at least one of those two nodes is infected by malware, both nodes will be infected by malware. This spread of malware will continue until no more nodes can be infected in this manner.

Suppose M(initial) is the final number of nodes infected with malware in the entire network after the spread of malware stops.

We will remove exactly one node from initial, completely removing it and any connections from this node to any other node.

Return the node that, if removed, would minimize M(initial). If multiple nodes could be removed to minimize M(initial), return such a node with the smallest index.

&nbsp;
Example 1:
Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0
Example 2:
Input: graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
Output: 1
Example 3:
Input: graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
Output: 1

&nbsp;
Constraints:


	n == graph.length
	n == graph[i].length
	2 &lt;= n &lt;= 300
	graph[i][j] is 0 or 1.
	graph[i][j] == graph[j][i]
	graph[i][i] == 1
	1 &lt;= initial.length &lt;&nbsp;n
	0 &lt;= initial[i] &lt;= n - 1
	All the integers in initial are unique.


from collections import defaultdict
from collections import deque
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        G = defaultdict(list)
        for v in range(n):
            for w in range(n):
                if graph[v][w]:
                    G[v].append(w)
                    
        affect = defaultdict(list)
        for s in initial:
            visited = set([v for v in initial if v != s])
            que = deque([s])
            while que:
                v = que.popleft()
                if v in visited: continue
                visited.add(v)
                affect[v].append(s)
                for w in G[v]:
                    que.append(w)
        res = [0]*n
        for v in affect:
            if len(affect[v]) == 1:
                res[affect[v].pop()] += 1
        if not max(res): return min(initial)
        return res.index(max(res))
class Solution {
    int[] parent;
    int[] size;
   
    public int find(int x){
        if(parent[x]==x) return x;
        int f = find(parent[x]);
        parent[x] = f;
        return f;
    }
    
    void merge(int x, int y){
        if(size[x]>size[y]){
            parent[y] = x;
            size[x] += size[y];
        }else{
            parent[x] =y;
            size[y] +=size[x];
        }
    }
    
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n =graph.length;
        
        parent = new int[n];
        size= new int[n];
        // putting initially infected nodes in hashset to ignore them while making graph
        HashSet<Integer> hs = new HashSet<>();
        for(int a : initial){
            hs.add(a);
        }
        //initializing Parent for DSU
        for(int i=0;i<parent.length;i++){
            parent[i] = i;
            size[i]=1;
        }
        //constructing groups DSU
        for(int i=0;i<graph.length;i++){
            for(int j=0;j<graph[0].length;j++){
                if(graph[i][j]==1 && !hs.contains(i) && !hs.contains(j)){
                    int p1 = find(i);
                    int p2 = find(j);
                    if(p1!=p2){
                        merge(p1,p2); //merging if they are not already
                    }
                }
            }
        }
        //Storing initial Nodes vs parents of connected node...if there are multiple edge to same component then we will get the same parent twice ...so we will take hashset for that purpose.
        HashMap<Integer,HashSet<Integer>> map = new HashMap<>();
        //We need to ensure increase the count whenever a parent is influenced by initial Nodes...because if it influenced by more than one infectious node then it would still remain infectious.
        int[] infected = new int[n]; 
        for(int e: initial){
            map.put(e,new HashSet<>());
            for(int j=0;j<n;j++){
                // in adjaceny graph[i][i] is always one so we will ignore that
                if(!hs.contains(j) && e!=j && graph[e][j]==1){ 
                    int p = find(j);
                    if(!map.get(e).contains(p)){
                        map.get(e).add(p);
                        infected[p]++;
                    }
                }
            }
        }
        int max = -1;
        int ans =-1;
        
        for(int e:initial){
            HashSet<Integer> par = map.get(e);
            int total =0;
            for(int p: par){
                if(infected[p]==1){ //add to total only if influenced by only one infectious node.
                    total+=size[p];
                }
            }
            if(total>=max){
                if(max==total){
                    ans = Math.min(ans,e);
                }else{
                    ans =e;
                }
                max =total;
            }
        }
        
        if(ans!=-1) return ans;
        //for returining smallest element.
        Arrays.sort(initial);
        
        return initial[0];
        
    }
}
class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        
        sort(initial.begin(), initial.end());
        int ans = -1, mn = INT_MAX, n = graph.size();
        
        vector<vector<int>> new_graph(n);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                if(graph[i][j])
                    new_graph[i].push_back(j);
        
        for(auto &k : initial)
        {
            vector<int> dsu(n, -1);
            for(int i = 0; i < n; i++)
                for(auto &j : new_graph[i])
                    if(i != k && j != k)
                    {
                        int a = findParent(dsu, i), b = findParent(dsu, j);
                        if(a != b)
                            dsu[b] += dsu[a], dsu[a] = b;
                    }
            
            vector<int> infected(n, 0);
            for(auto &i : initial)
                if(i != k)
                    infected[findParent(dsu, i)]++;
            
            int total_infected = 0;
            for(int i = 0; i < n; i++)
                if(infected[i])
                    total_infected += abs(dsu[i]);
            
            if(total_infected < mn)
                mn = total_infected, ans = k;
        }
        
        return ans == -1 ? initial[0] : ans;
    }
    
    int findParent(vector<int> &dsu, int i)
    {
        int a = i;
        while(dsu[i] >= 0)
            i = dsu[i];
        
        if(i != a)
            dsu[a] = i;
            
        return i;
    }
};
var minMalwareSpread = function(graph, initial) {
let n = graph.length
let AdjList = new Map();
let listFromGraph = (mat) => {// convert adj matrix to adj list
    for(let i=0; i<n; i++){
        AdjList[i] = [];
        for(let j=0; j<n; j++){
            if(mat[i][j] === 1 && i!==j){
                AdjList[i].push(j);
            }
        }
    }
}
listFromGraph(graph);
let visitedSet = new Set();//visited set, to manage the visited nodes & their count as they are unique
let dfs = (curr,node) => {// dfs helper, visit the graph assuming that node, given as 2nd parameter is deleted
    if(curr===node){
        return;
    }
    if(visitedSet.has(curr)){
        return;
    }
    visitedSet.add(curr);// size of visited shows how many nodes are visited/affected by the malware
    let neighbours = AdjList[curr];
    for(let i in neighbours){// visit all the neighbours
        dfs(neighbours[i],node);
    }
}
let MinSpread = n;// min index of node with max reduction in malware
let SpreadDist = n;// number of nodes affected by malware if MinSpread was deleted
for(let i=0; i<initial.length; i++){
    for(let j=0; j<initial.length; j++){// find the total nodes affected if ith node is removed
        dfs(initial[j],initial[i]);
    }
    if(SpreadDist == visitedSet.size){// to get min index but same impact
        MinSpread = Math.min(initial[i],MinSpread);
    }
    if(SpreadDist > visitedSet.size){// to get max impact
        MinSpread = initial[i];
        SpreadDist = visitedSet.size;
    }
    visitedSet.clear();// clear visited set for next index to be deleted
}
return MinSpread;
};
Minimize Malware Spread II