// Runtime: 19 ms (Top 23.81%) | Memory: 127.5 MB (Top 49.76%)
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];
        }
    }
}