Share my 3ms Union-find solution with important explanation.!!!


  • 1
    Y
    public boolean validTree(int n, int[][] edges) {
        int[] roots = new int[n];
        for(int i = 0; i < n; i++) roots[i] = i;
        for(int[] e : edges){
            int root1 = find(roots,e[0]);
            int root2 = find(roots,e[1]);
            if(root1 != root2) {
                roots[root1]= root2;
                n --;
            }
            else{
                
                return false;
            }
        }
        if(n == 1)        // It is very important. The question just asks one valid tree
        return true;    // if there are two or more valid connected components, it's still false.
        else{              // if n == 0, that means there are n points, and n edges. there must be a cycle.
            return false;
        }
    }
    public int find(int[] roots, int index){
        while(roots[index] != index){
            roots[index] = roots[roots[index]];
            index = roots[index];
        }
        return roots[index];
    }

Log in to reply
 

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