Java Easy Solution, beats 85.94% , union find and compress path


  • 2
    B
    public boolean validTree(int n, int[][] edges) {
        int[] root = new int[n];
        for(int i = 0; i < n; i++) {
            root[i] = i;
        }
        for(int[] edge : edges) {
            
            int root1 = find(root, edge[0]);
            int root2 = find(root, edge[1]);
            if(root1 == root2) {
                return false;
            }
            root[root1] = root2;
        }
        return edges.length == n - 1;
    }
    private int find(int[] root, int p) {
        while(root[p] != p) {
            root[p] = root[root[p]];
            p = root[p];
        }
        return p;
    }

  • 2

    Does it really do path compression? I understand that path compression means setting every node's parent up the hierarchy to the root. But this looks like it only sets it to the parent's parent, which seems like only partial path compression.


  • 0
    H

    This isn't traditional path compression, where we take the subtree of a node and make it a subtree of its highest parent.
    Please correct me if I'm wrong.

      3
     /
    1
     \ 
      4
    
    becomes
    
      3
     /  \
    1   4
    

Log in to reply
 

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