Very simple AC Java Solution - Union Find


  • 0
    D
    public boolean validTree(int n, int[][] edges) {
        int[] roots = new int[n];
        for(int i = 0; i < roots.length; i++) roots[i] = i;
        
        for(int[] edge: edges){
            int root1 = findRoot(roots, edge[0]), root2 = findRoot(roots, edge[1]);
            //if those two nodes are already connected, return false
            if(root1 == root2)  return false;
            roots[root2] = root1;
        }
        // return true if number of tree is 1
        int tree = 0;
        for(int i = 0; i < n; i++){
            if(roots[i] == i) tree++;
        }
        return tree == 1;
    }
    
    public int findRoot(int[] roots, int i){
        while(roots[i] != i){
            roots[i] = roots[roots[i]];
            i = roots[i];
        }
        return i;
    }

Log in to reply
 

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