public class Solution {
public boolean validTree(int n, int[][] edges) {
// initialize n isolated islands
int[] nums = new int[n];
Arrays.fill(nums, 1);
// perform union find
for (int i = 0; i < edges.length; i++) {
int x = find(nums, edges[i][0]);
int y = find(nums, edges[i][1]);
// if two vertices happen to be in the same set
// then there's a cycle
if (x == y) return false;
// union
nums[x] = y;
}
return edges.length == n  1;
}
int find(int nums[], int i) {
if (nums[i] == 1) return i;
return find(nums, nums[i]);
}
}
AC Java UnionFind solution


Hi Steven,
There is good resource for learning this classic algorithm:
https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdfI think there may be a little obstacle in understanding Jeantimex's solution of tracing back a node's set number through DFS. I have made following analysis, hope it helps.
Suppose we have already known "node_m" in the set "0" and we update the union array through following way,
int x = findUnion(union, edge[0]);
int y = findUnion(union, edge[1]);
union[y] = x;Two possible cases for a new edge.
Case 1: [node_m node_n]
Case 2: [node_n node_m]For case 1:
x = findUnion(union, node_m) = 0;
y = findUnion(union, node_n) = node_n;
union[node_n] = 0;
When we use DFS method, we can trace node_n's set number is 0.For case 2:
x = findUnion(union, node_n) = node_n;
y = findUnion(union, node_m) = 0;
union[0] = node_n
When we use DFS method, we can trace all explored nodes in the set back to set node_n.

Hi Steven, for detailed explanation, I recommend this article from geeksforgeeks: http://www.geeksforgeeks.org/unionfind/

Is it right to resolve it by:
https://en.wikipedia.org/wiki/Seven_Bridges_of_Königsbergpublic boolean validTree(int n, int[][] edges) { final Set<Integer> set = new HashSet<>(); for (int i = 0, len = edges.length; i < len; i++) { if (set.add(edges[i][0]) == false) { set.remove(edges[i][0]); } if (set.add(edges[i][1]) == false) { set.remove(edges[i][1]); } if (set.size() == 0) { return false; } } return edges.length == n  1; }

Below is just a more complete(verbose) version.
But I still prefer @jeantimex's solution. It's better for interview.First define the UnionFind class, with some optimization: weighted quickunion and path compression. This will greatly reduce the time complexity of union and find operations. See the reference link below. Read thru it. It's very useful.
Then solve the problem is very straightforward.
reference: https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdfclass UF { // unionfind, bfs int N; int[] id; int[] sz; int segments; public UF(int n){ N = n; segments = n; id = new int[N]; sz = new int[N]; for(int i=0; i<N; i++){ id[i] = i; sz[i] = 1; } } public int root(int i) { while(i!=id[i]){ id[i] = id[id[i]]; // path compression i = id[i]; } return i; } public void connect(int p, int q){ int i = root(p); int j = root(q); if(i == j) return; if(sz[i]<sz[j]) { // ifelse: weighted quickunion id[i] = j; sz[j] += sz[i]; } else if(sz[i]>sz[j]) { id[j] = i; sz[i] += sz[j]; } else { id[j] = i; sz[i] += sz[j]; } segments; } public boolean connected(int p, int q) { if(root(p)==root(q)){ return true; } return false; } } public class Solution { public boolean validTree(int n, int[][] edges) { UF uf = new UF(n); int M = edges.length; for(int i=0; i<M; i++){ int p = edges[i][0], q = edges[i][1]; if(uf.root(p)==uf.root(q)){ return false; } uf.connect(p, q); } if (uf.segments!=1){ return false; } return true; } }

share my solution. I "randomized" the merge of union sets
public class Solution { public boolean validTree(int n, int[][] edges) { if (edges.length != n  1) return false; UnionSet us = new UnionSet(n); for (int[] edge : edges) if (!us.merge(edge[0], edge[1])) return false; return true; } private class UnionSet { private int[] p; public UnionSet(int n) { p = new int[n]; for (int i = 0; i < n; i++) p[i] = i; } public int find(int i) { if (p[i] != i) p[i] = find(p[i]); return p[i]; } public boolean merge(int i, int j) { int a = find(i), b = find(j); if (a == b) return false; if ((a & 1) == 0) p[a] = b; else p[b] = a; // randomize the merge return true; } } }