Graph Valid Tree — Union Find Cycle Check
Treat the graph as a disjoint set; every edge must connect two different components and the graph needs exactly n − 1 edges.
Problem Statement
Given n nodes labeled 0..n-1 and undirected edges, determine whether they form a valid tree.
Why This Problem Matters
- Illustrates how trees are acyclic, fully connected graphs—two constraints you can test independently.
- Union-Find is a reusable tool for detecting cycles in undirected graphs in near-linear time.
- This question opens the door to discussing spanning trees and graph connectivity proofs.
Thought Process
Check edge counts first
A tree with n nodes must have exactly n − 1 edges; anything else fails immediately.
Use Disjoint Set Union (DSU)
Start each node in its own set and union endpoints; a failed union indicates a cycle.
Track connectivity
After processing all edges, the DSU should report a single connected component.
Reason about complexity
Path compression and union by size keep operations almost constant, so the whole check is linear.
Step-by-Step Reasoning
- Return false early if edges.length != n - 1.
- Initialise a disjoint-set structure with n singleton components.
- For each edge (u, v) attempt to union the endpoints; if union returns false a cycle exists.
- When all edges are processed, ensure the DSU reports exactly one component.
Dry Run
n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Every union succeeds and components drop to 1 → tree.
Add edge [1,3] afterwards
union(1,3) finds both in same set and returns false, exposing the cycle.
Complexity Analysis
Time
O(n α(n))
Space
O(n)
Why
Each union/find is inverse-Ackermann time; DSU arrays store parent, size, and component counts.
Annotated Solution
public class GraphValidTree {
public boolean validTree(int n, int[][] edges) {
if (edges.length != n - 1) {
return false;
}
DisjointSet ds = new DisjointSet(n);
for (int[] edge : edges) {
if (!ds.union(edge[0], edge[1])) {
return false;
}
}
return ds.components() == 1;
}
private static class DisjointSet {
private final int[] parent;
private final int[] size;
private int components;
DisjointSet(int n) {
parent = new int[n];
size = new int[n];
components = n;
for (int i = 0; i < n; i += 1) {
parent[i] = i;
size[i] = 1;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
boolean union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) {
return false;
}
if (size[rootA] < size[rootB]) {
int temp = rootA;
rootA = rootB;
rootB = temp;
}
parent[rootB] = rootA;
size[rootA] += size[rootB];
components -= 1;
return true;
}
int components() {
return components;
}
}
}The DSU merges components while guarding against cycles. If an edge connects two nodes already in the same set, the graph cannot be a tree.
Common Pitfalls
- Skipping the n − 1 edge check lets disconnected graphs with no cycles slip through.
- Forgetting path compression or union by size can degrade performance on adversarial inputs.
- Treating the graph as directed changes the definition of cycle detection entirely.
Follow-Up Questions
- How would you return the specific edge that closes the cycle?
- Can you rewrite the solution with DFS and parent tracking instead of DSU?