Graph Valid Tree
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
Example
Givenn = 5andedges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.
Code:
public class Solution {
public boolean validTree(int n, int[][] edges) {
if (edges.length != n - 1) {
return false;
}
UnionFind uf = new UnionFind(n);
for (int i = 0; i < edges.length; i++) {
int a = uf.find(edges[i][0]);
int b = uf.find(edges[i][1]);
if (a == b) {
return false;
}
uf.union(a, b);
}
return true;
}
class UnionFind {
private int[] father;
public UnionFind(int n) {
father = new int[n];
for (int i = 0; i < n; i++) {
father[i] = i;
}
}
public int find(int i) {
int parent = father[i];
while (parent != father[parent]) {
parent = father[parent];
}
//update
int temp = -1;
int fa = father[i];
while (fa != father[fa]) {
temp = father[fa];
father[fa] = parent;
fa = temp;
}
return parent;
}
public void union(int a, int b) {
int parentA = find(a);
int parentB = find(b);
father[parentB] = parentA;
}
}
}