The problem is Union Find.
Is there any 3 elements that determine whether some sides are tree?
1. The number of edges is not the number of points -1?
2. Each side can not be joined by ring; (when adding edge to do check).
3. When all sides are joined, the edges must be connected; (all sides are added to see the number of Union).
First, define the class of UnionFind. Defining interface
class UnionFind{ int[] father; int size; public UnionFind(int size){ father = new int[size]; for(int i = 0 ; i < size; ++i){ father[i] = i; } this.size = size; } public void union(int a, int b){ int father_a = findRoot(a); int father_b = findRoot(b); if(father_a != father_b){ father[father_a] = father_b; size--; } } public int findRoot(int a){ while(father[a] != a){ father[a] = father[father[a]]; a = father[a]; } return a; } }
The main function only needs to call our class.
public boolean validTree(int n, int[][] edges) { // edge have to be n-1 node if(n-1 != edges.length) return false; //doing union find for all edges. UnionFind uf = new UnionFind(n); for(int[] edge: edges){ int n1 = edge[0]; int n2 = edge[1]; if(uf.findRoot(n1) == uf.findRoot(n2)){ return false; } uf.union(n1, n2); } return uf.size == 1; }