[0, 1, 2, 3, 4]parent
A graph is a valid tree iff it has exactly n−1 edges and is fully connected with no cycles. Union-Find lets you check both conditions in a single pass: each edge either merges two components (good) or connects two nodes already in the same component (cycle — bad).
Given n nodes (labeled 0 to n−1) and a list of undirected edges, return true if the edges form a valid tree. A valid tree has no cycles and is fully connected — every node is reachable from every other. Example: n=5, edges=[[0,1],[0,2],[0,3],[1,4]] → true. If you add edge [2,4] you get a cycle → false.
edges.length !== n − 1, return false immediately — too few means disconnected, too many means a cycle exists.parent[i] = i so each node is its own component. Optionally maintain a rank array for union by rank.[a, b], call find(a) and find(b). If their roots are equal, they're already connected — a cycle exists, return false. Otherwise call union to merge the components.Both are accepted. Union-Find with path compression and union-by-rank runs in O(n · α(n)) where α is the inverse Ackermann function — practically O(n). DFS is simpler to write and also O(n + e) but has recursive overhead and requires careful "parent" tracking to avoid treating the undirected back-edge as a false cycle.
n=5, 4 edges (need exactly 4 for a tree). Running Union-Find.[0, 1, 2, 3, 4]function validTree(n: number, edges: number[][]): boolean {
// A valid tree has exactly n-1 edges AND is fully connected (no cycles).
if (edges.length !== n - 1) return false;
const parent: number[] = Array.from({ length: n }, (_, i) => i);
const rank: number[] = new Array(n).fill(0);
function find(x: number): number {
while (parent[x] !== x) {
parent[x] = parent[parent[x]]; // path compression (halving)
x = parent[x];
}
return x;
}
function union(a: number, b: number): boolean {
const ra = find(a);
const rb = find(b);
if (ra === rb) return false; // already in the same component → cycle
if (rank[ra] < rank[rb]) {
parent[ra] = rb;
} else if (rank[ra] > rank[rb]) {
parent[rb] = ra;
} else {
parent[rb] = ra;
rank[ra]++;
}
return true;
}
for (const [a, b] of edges) {
if (!union(a, b)) return false; // cycle found
}
return true; // n-1 edges, no cycle → connected tree
}n nodes must have exactly n−1 edges. Checking this first eliminates impossible inputs before any expensive work. Too few edges → disconnected; too many → at least one cycle.parent[i] = i makes each node its own root. The rank array controls tree height during union to keep find fast.parent chain until we reach a root. Path halving (parent[x] = parent[parent[x]]) flattens the tree lazily, keeping future find calls O(α(n)).[a, b], call union(a, b). If it returns false, the two nodes share a root → adding this edge would create a cycle → return false immediately.parent and rank arrays.false, return the offending [a, b].parent. You could destructively modify an adjacency list in-place but that's impractical.edges.length === 0 === n−1passes the check, the loop doesn't execute, and we return true correctly.| "valid tree" / "no cycle + connected" | edge count check + Union-Find |
| "connected components" in undirected graph | Union-Find with find/union |
| "redundant edge" / merge groups | Union-Find — return the bad edge |
| cycle detection in undirected graph | Union-Find or DFS with parent tracking |
if (edges.length !== n - 1) return false;
const parent = Array.from({ length: n }, (_, i) => i);
const rank = new Array(n).fill(0);
function find(x: number): number {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
for (const [a, b] of edges) {
const ra = find(a), rb = find(b);
if (ra === rb) return false; // cycle
// union by rank ...
}
return true;n=5 and edges=[[0,1],[0,2],[0,3],[1,4]], what does validTree return?find(2) and find(4) for edge [2,4] and both return 0. What happens next?n=4 and edges=[[0,1],[2,3]]. What does validTree return and why?parent[x] = parent[parent[x]]. What does this accomplish?