Weighted Quick Union with path compression


  • 0
    public class Solution {
         int [] arr ;
         int [] sz;
        public boolean validTree(int n, int[][] edges) {
             arr = new int[n];
             sz =new int[n];
            for(int i=0;i<n;i++){ arr[i]=i;sz[i]=1;}
            for(int i=0;i<edges.length;i++)
            {
                if(connected(edges[i][0],edges[i][1]))
                return false;
                union(edges[i][0],edges[i][1]);
            }
            int count=0;
            for(int i=0;i<n&&count<=1;i++)
            {
             if(arr[i]==i) count++;   
            }
            return count<=1;
        }
        
        public int root(int i)
        {
            while(arr[i]!=i)
            {
                arr[i]=arr[arr[i]]; // path compression
                i=arr[i];
            }
            return i;
        }
        
        public boolean connected(int p, int q )
        {
            return root(p)==root(q);
        }
        public void union(int p, int q)
        {
            int i=root(p);
            int j=root(q);
            if(i==j) return;
            if(sz[i]<sz[j]) {
                arr[i]=j;
                sz[j]+=sz[i];     // weighted  quick-union
            }
            else{
                arr[j]=i;
                sz[i]+=sz[j];
            }
        }
    }
    

Log in to reply
 

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