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.
For example:
Given
n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given
n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.
Hint:
- Given
n = 5andedges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree? - According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
Note: you can assume that no duplicate edges will appear in
edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.First, the graph should not contain cycle. Second, all nodes should connect to each other. The easiest way is to use union find. After all unions of edges, the size should be only 1.
public boolean validTree(int n, int[][] edges) {
UnionFind unionFind = new UnionFind(n);
for (int[] e : edges) {
if (!unionFind.union(e[0], e[1])) {
return false;
}
}
return unionFind.size == 1;
}
private class UnionFind {
int[] vertices;
int size = 0;
public UnionFind(int n) {
vertices = new int[n];
Arrays.fill(vertices, -1);
size = n;
}
public int find(int v) {
validate(v);
if (vertices[v] < 0) {
return v;
}
vertices[v] = find(vertices[v]);
return vertices[v];
}
public boolean union(int u, int v) {
int uR = find(u);
int vR = find(v);
if (uR == vR) {
return false;
}
if (vertices[vR] < vertices[uR]) {
vertices[uR] = v;
} else {
if (vertices[vR] == vertices[uR]) {
vertices[uR]--;
}
vertices[vR] = u;
}
size--;
return true;
}
private void validate(int v) {
if (v < 0 || v >= vertices.length) {
throw new InvalidParameterException("Invalid input!");
}
}
}