# Java Union-Find solution - QuickUnion

• Updated: Thanks for pointing it out @StefanPochmann

``````public class Solution {
public boolean validTree(int n, int[][] edges) {

if(n <= 0)
return false;

if(edges == null || edges.length != n-1)
return false;

int[] unionFind = new int[n];

for(int i = 0 ; i < n ; i++){
unionFind[i] = i;
}

for(int i = 0 ; i < edges.length ; i++){
int x = edges[i][0];
int y = edges[i][1];

if(findRoot(unionFind, x) == findRoot(unionFind, y))
return false;
unionFind[y] = x;
}

return true;

}

int findRoot(int[] unionFind, int i){
while(i != unionFind[i])
i = unionFind[i];

return i;
}
``````

}

• Doesn't work, for example fails this case:

4
[[0,1],[2,0],[1,2]]

• Thanks! Corrected it

• Still not work on:
5
[[0,1],[2,1],[2,0],[2,4]].

Guess it's because when it reads in [2,1], the code will set unionFind[1] = 2. But the root of 1 is supposed to be 0. If you set it to 2, you disconnect it with 0.

This modification will make the code work.
int x = Math.min(edges[i][0], edges[i][1]);
int y = Math.max(edges[i][0], edges[i][1]);

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