Leetcode 323) Number of Connected Components in an Undirected Graph

13 Oct 2021 in Algorithms

My Answer

class Solution {
    public int countComponents(int n, int[][] edges) {
        int cnt =0; 
        boolean[] visited = new boolean[n];     
        List[] links = new ArrayList[n];

        //Initialize adjacency list
        for(int i=0;i<n;i++){
            links[i]= new ArrayList<Integer>();
        }

        //complete adjacency list
        for(int i=0;i<edges.length;i++){
            links[edges[i][0]].add(edges[i][1]);
            links[edges[i][1]].add(edges[i][0]);
        }



        //travel all the edges
        for(int i =0;i<n;i++){
            if(!visited[i]){
                visited[i]=true;
                cnt++;
                explore(i,visited,links);
            }
        }
        return cnt;
    }
    public void explore(int i , boolean[] visited,List[] links){
        visited[i]=true;
        for(int j =0;j<links[i].size();j++){
            if(!visited[(int)links[i].get(j)]){
                explore((int)links[i].get(j),visited,links); 
            }
        }
    }

}

Other Answer

class Solution {
    int cnt;
    public int countComponents(int n, int[][] edges) {
        int[] root = new int[n];
        cnt=0;
        //initialize the head 
        for(int i =0;i<n;i++){
            root[i]=-1;
        }               
        //update head by checking edges
        for(int i=0;i<edges.length;i++){
            updateRoot(edges[i],root);
        }
        for(int i =0;i<n;i++){
            if(root[i]==-1){cnt++;}
        }
        return cnt;
    }

    public void updateRoot(int[] edge, int[] root){
        if(root[edge[0]]==-1 && root[edge[1]]==-1 ){
            cnt++;
            root[edge[0]]=edge[0];
            root[edge[1]]=edge[0];
        }else if(root[edge[0]]==-1){
            //root[1]!=-1, root array will always contain initial root (we will update anytime if there is a new root found)
            root[edge[0]]=root[edge[1]];
        }else if(root[edge[1]]==-1){
            root[edge[1]]=root[edge[0]];
        }else{
            if(root[edge[0]]!=root[edge[1]]){
                cnt--;
                //both has root, so we conbine it
                int fix =root[edge[1]];
                for(int i =0;i<root.length;i++){
                    //(root[i]==root[edge[1]])
                    if(root[i]==fix){
                        root[i]= root[edge[0]];
                    }
                }
            }
        }
    }
}