Q35 Minimize Malware Spread - LeetCode 924

class Solution {
    int parents[] ;
    int size [];
    
    public int findparent(int u){
        if(parents[u] == u)
        return u;

        int temp = findparent(parents[u]);
        parents[u] = temp;

        return temp;
    }

    public void merge(int p1 , int p2 ){
        
        if(size[p1] > size[p2]){
            parents[p2] = p1;
            size[p1] += size[p2];
        }
        

        else{
            parents[p1] = p2;
            size[p2] += size[p1];
        }
        

    }
    public int minMalwareSpread(int[][] graph, int[] initial) {
        /* Q35 of graph playlist, DSU concept .
        1) find components and merge them using DSU 
        2) here rank will be equal to size denoting size of the component
        
        3) find parent of infected index and then their size and update answer accordingly
        */
        
        int m = graph.length , n = graph[0].length;
        parents = new int[m];
        size = new int[m];

        for(int i = 0 ;i < m ; i++){
            parents[i] = i;
            size[i] = 1;
        }

        //merging nodes and finding components and updating size of components
        for(int i = 0 ; i < m ; i ++){
            for(int j = 0 ;j < n ; j++){
                
                //if edge is present merge
                if(graph[i][j] ==1){
                    int p1 = findparent(i);
                    int p2 = findparent(j);

                    if(p1 != p2)
                    merge(p1 , p2);
                }
            }
        }

        //making hashset to prevent duplicate answer 
        HashSet<Integer> set = new HashSet<>();
        int ans = Integer.MAX_VALUE, max_size = -1;

        //finding answer for virus 
        for(int virus : initial){
            int p1 = findparent(virus);

            if(size[p1] > max_size){
                ans = virus ;
                max_size = size[p1];
            }

            else if(size[p1] == max_size && virus < ans)
            ans = virus;
        }

        return ans;
    }
}