2ms O(n) UnionFind solution with weighted union and path compression


  • 0
    U
    public boolean validTree(int n, int[][] edges) {
        int[] unionFind = new int[n];// unionFind dataStructure.
        for(int i=0;i<n;i++)
            unionFind[i]=i;
        int m= edges.length;
        int[] sz= new int[n];
        Arrays.fill(sz,1);
        int maxSize=1;// # of largest group
        
        for(int i=0;i<m;i++){
            int index1=edges[i][0];
            int index2=edges[i][1];
            if(connect(unionFind, index1, index2))
                return false;
            
            maxSize= union(sz, unionFind, index1, index2, maxSize);
        }
        
        return maxSize==n;//if maxSize!=n means there is another group.
        
    }
    // weighted union
    private int union(int[] sz, int[] unionFind, int index1, int index2, int maxSize){
        int root1=find(unionFind,index1);
        int root2=find(unionFind,index2);
        if(sz[root1]<sz[root2]){
            unionFind[root1]=root2;
            sz[root2]+=sz[root1];
        }
        else{
            unionFind[root2]=root1;
            sz[root1]+=sz[root2];
        }
        if(Math.max(sz[root1],sz[root2])>maxSize)
            maxSize=Math.max(sz[root1],sz[root2]);
        
        return maxSize;
    }
    
    private boolean connect(int[] unionFind, int index1, int index2){
        int root1=find(unionFind,index1);
        int root2=find(unionFind,index2);
        if(root1==root2)
            return true;
        else 
            return false;
        
    }
    private int find(int[] unionFind, int i){
        while(i!=unionFind[i]){
            unionFind[i]=unionFind[unionFind[i]];// path compression
            i=unionFind[i];
        }
        return i;
    }

Log in to reply
 

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