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

• 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;
}

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