Java Union find


  • 0
    H
       public int findCircleNum(int[][] M) {
            int circle = M.length;
            int[] roots = new int[M.length];
            for(int i=0;i<roots.length;i++){
                roots[i] = i;
            }
            for(int i=0;i<M.length;i++){
                for(int j=i+1;j<M.length;j++){
                    if(M[i][j] == 1){
                        int root1 = find(i, roots);
                        int root2 = find(j, roots);
                        if(root1 != root2) {
                            roots[root1] = root2; // union
                            circle--;
                        }
                    }
                }
            }
            return circle<=0?1:circle;
        }
    
        private int find(int id, int[] roots){
            while(roots[id] != id) {
                roots[id] = roots[roots[id]];  // optional: path compression
                id = roots[id];
            }
            return id;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.