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.

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.

Note that if a node was removed from the initial list of infected nodes, it might still be infected later due to the malware spread.

&nbsp;
Example 1:
Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0
Example 2:
Input: graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
Output: 0
Example 3:
Input: graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
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;= n
	0 &lt;= initial[i] &lt;= n - 1
	All the integers in initial are unique.


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        uf = UnionFind(n)
        for i in range(n):
            for j in range(n):
                if graph[i][j]:
                    uf.union(i, j)

        max_remove = 0

        initial.sort()
        min_index = initial[0]
        for i in range(len(initial)):
            cur_remove = 0
            linked = False
            for j in range(len(initial)):
                if i == j: continue
                if uf.find(initial[i]) == uf.find(initial[j]):
                    linked = True
            if not linked:
                cur_remove = uf.rank[uf.find(initial[i])]
                if max_remove < cur_remove:
                    max_remove = cur_remove
                    min_index = initial[i]

        return min_index

class UnionFind:
    def __init__(self, size):
        self.parent = {}
        self.rank = {}
        for i in range(size):
            self.parent[i] = i
            self.rank[i] = 1

    def find(self, x):
        if x != self.parent[x]:
            x = self.find(self.parent[x])
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return
        if self.rank[px] >= self.rank[py]:
            self.parent[py] = px
            self.rank[px] += self.rank[py]
        else:
            self.parent[px] = py
            self.rank[py] += self.rank[px]
class Solution {
    int[]parent;
    int[]size;

    public int minMalwareSpread(int[][] graph, int[] initial) {
        parent = new int[graph.length];
        size = new int[graph.length];
        for(int i=0;i<parent.length;i++){
            parent[i] = i;
            size[i] = 1;
        }

        for(int i=0;i<graph.length;i++){
            for(int j=0;j<graph[0].length;j++){
                if(i != j && graph[i][j] == 1){
                    unionHelper(i,j);
                }
            }
        }

        int []imap = new int[graph.length];
        for(int val : initial){
            int ri = find(val);
            imap[ri]++;
        }

        int ans_i = -1;
        int ans_size = 0;
        for(int i:initial){
            int ri = find(i);
            if(imap[ri] == 1){
                if(ans_i == -1){
                        ans_i = i;
                        ans_size = size[ri];
                }else if(size[ri] > ans_size){
                        ans_i = i;
                        ans_size = size[ri];
                }else if(size[ri] == ans_size){
                    if(i < ans_i){
                        ans_i = i;
                        ans_size = size[ri];
                    }
                }
            }
        }

        if(ans_i == -1){
            ans_i = graph.length;
            for(int i : initial){
                if(i < ans_i){
                    ans_i = i;
                }
            }
        }

        return ans_i;

    }

    int find(int x){
        if(parent[x] == x){
            return x;
        }else{
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }

    void unionHelper(int x,int y){
        int xl = find(x);
        int yl = find(y);

        if(size[xl] < size[yl]){
            parent[xl] = yl;
            size[yl] += size[xl];
        }else{
            parent[yl] = xl;
            size[xl] += size[yl];
        }
    }
}
class Solution {
public:
    void dfs(int i,int n,vector<bool> &visited,vector<int>&cur,map<int,int>& ind,int &cnt,map<int,vector<int> >&mp)
    {
        if(!visited[i])
        {
            visited[i]=true;
            cur.push_back(i);
            ind[i]=cnt;
            for(int j=0;j<mp[i].size();j++)
            {
                dfs(mp[i][j],n,visited,cur,ind,cnt,mp);
            }
        }
    }
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
         int n=graph.size();
         map<int,vector<int> > mp; //Adjacency list creation for the graph
         for(int i=0;i<n;i++)
         {
             for(int j=0;j<n;j++)
             {
                 if(i!=j && graph[i][j]==1)
                     mp[i].push_back(j);

             }
         }
        map<int,int> ind; // This map is for storing the component number to which a particular node belongs to
        vector<vector<int> > v; //Store all the connected components
        vector<bool> visited(n,false); //Visited array to keep track of the visited nodes
        int cnt=0;//Current component number
        for(int i=0;i<n;i++)
        {
            if(!visited[i])
            {
                vector<int> cur;
                dfs(i,n,visited,cur,ind,cnt,mp);//Dfs call for getting single components
                cnt++;
                v.push_back(cur);
            }
        }
    map<int,vector<int> > help; //This map tells that how many node that is present in inital vector are of same component
        for(int i=0;i<initial.size();i++)
        {
            int index=ind[initial[i]];
            help[index].push_back(initial[i]);
        }
        int sz=INT_MIN;
        int ans=n;//This loop is based on the logic described above
        for(auto it=help.begin();it!=help.end();it++)
        {
            if(help[it->first].size()==1)
            {
                int cover=v[it->first].size();
                if(cover>sz)
                {
                    sz=cover;
                    ans=help[it->first][0];
                }
                else if(cover==sz)
                {
                    if(help[it->first][0]<ans)
                        ans=help[it->first][0];
                }
            }
        }
        if(ans!=n)
            return ans;
        for(int i=0;i<initial.size();i++)
            ans=min(ans,initial[i]);
        return ans;

    }
};
var minMalwareSpread = function(graph, initial) {
  let n = graph.length, uf = new UnionFind(n);
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (graph[i][j]) uf.union(i, j);
    }
  }
  
  // Get number of nodes in each connected component
  let nodesCount = {};
  for (let i = 0; i < n; i++) {
    let parent = uf.find(i);
    nodesCount[parent] = (nodesCount[parent] || 0) + 1;
  }
  
  // Find the initial node connected to the most amount of other nodes, where it is the only malware infected node in its group.
  let max = 0, res = Infinity;
  for (let node of initial) {
    let malwareNodes = malwareConnected(node);
    let parent = uf.find(node);
    let nodesAffected = malwareNodes === 1 ? nodesCount[parent] : 0;
    if (nodesAffected > max || (nodesAffected === max && node < res)) {
      res = node;
      max = nodesAffected;
    }
  }
  return res;
  
  function malwareConnected(node) { // gets number of malware infected nodes connected to node
    let count = 0;
    for (let malware of initial) {
      if (uf.isConnected(node, malware)) count++;
    }
    return count;
  }
};

class UnionFind {
  constructor(size) {
    this.rank = Array(size);
    this.root = Array(size);
    for (let i = 0; i < size; i++) {
      this.rank[i] = 1;
      this.root[i] = i;
    }
  }
  find(x) {
    if (this.root[x] === x) return x;
    return this.root[x] = this.find(this.root[x]);
  }
  union(x, y) {
    let rootX = this.find(x), rootY = this.find(y);
    if (rootX === rootY) return false;
    if (this.rank[rootX] < this.rank[rootY]) this.root[rootX] = rootY;
    else if (this.rank[rootX] > this.rank[rootY]) this.root[rootY] = rootX;
    else {
      this.root[rootY] = rootX;
      this.rank[rootX]++;
    }
    return true;
  }
  isConnected(x, y) {
    return this.find(x) === this.find(y);
  }
}
Minimize Malware Spread