261_Graph_Valid_Tree.java

classSolution {
publicbooleanvalidTree(intn, int[][] edges) {
int[] parents = newint[n];

for (inti = 0; i < parents.length; i++) {
parents[i] = i;
 }

for (int[] edge : edges) {
intp1 = findParent(parents, edge[0]);
intp2 = findParent(parents, edge[1]);

if (p1 == p2) {
returnfalse;
 }

union(parents, p1, p2);
 --n;
 }

returnn == 1;
 }

privateintfindParent(int[] parents, intnode) {
if (parents[node] == node) {
returnparents[node];
 }

parents[node] = findParent(parents, parents[node]);
returnparents[node];
 }

privatevoidunion(int[] parents, intp1, intp2) {
parents[p2] = parents[p1];
 }
}