Detect a cycle in a graph using Union-Find
Walk a small undirected graph edge by edge, using Union-Find to flag the first edge that creates a cycle. The same machinery powers Kruskal’s MST.
concept: Union-Find
Problem
You're given an undirected graph on 6 vertices labeled 0..5. Edges arrive one at a time, in this order:
(0, 1), (2, 3), (1, 2), (3, 4), (4, 5), (1, 4)
For each edge, decide whether adding it to the graph creates a cycle. Use Union-Find with both union-by-rank and path compression.
Approach
An edge (u, v) creates a cycle exactly when u and v are already in the same connected component. So we walk the edge list and check find(u) == find(v) at each step. If they're equal, we've found a cycle. Otherwise, we union them and move on.
Initial state: six singletons.
parent = [0, 1, 2, 3, 4, 5]
rank = [0, 0, 0, 0, 0, 0]Walkthrough
find(0) = 0, find(1) = 1. Different roots → no cycle.
Union: ranks tie at 0. Attach parent[1] = 0, bump rank[0] to 1.
parent = [0, 0, 2, 3, 4, 5]
rank = [1, 0, 0, 0, 0, 0]find(2) = 2, find(3) = 3. Different → no cycle.
Ranks tie at 0. Attach parent[3] = 2, bump rank[2] to 1.
parent = [0, 0, 2, 2, 4, 5]
rank = [1, 0, 1, 0, 0, 0]find(1): walk 1 → 0. Root = 0.
find(2): 2 is already a root. Root = 2.
Different → no cycle. Union: both roots have rank 1 — tie. Attach parent[2] = 0, bump rank[0] to 2.
parent = [0, 0, 0, 2, 4, 5]
rank = [2, 0, 1, 0, 0, 0]Notice that node 3 still points at 2, which now points at 0 — so node 3 is now two hops from its root. The chain hasn't been compressed yet, because no find has walked through it.
find(3): walk 3 → 2 → 0. Root = 0.
Path compression fires on the way back: rewire parent[3] and parent[2] to point directly at 0.
find(4) = 4. Different → no cycle. Union: rank[0] = 2 > rank[4] = 0. Attach parent[4] = 0.
parent = [0, 0, 0, 0, 0, 5]
rank = [2, 0, 1, 0, 0, 0]find(4) = 0, find(5) = 5. Different → no cycle.
Union: rank[0] = 2 > rank[5] = 0. Attach parent[5] = 0.
parent = [0, 0, 0, 0, 0, 0]
rank = [2, 0, 1, 0, 0, 0]find(1) = 0 (one hop, already compressed).
find(4) = 0.
Same root — cycle detected. Skip the edge; don't union.
The first cycle-creating edge in the sequence is edge 6: (1, 4). Edges 1 through 5 were all safe to add — each connected two previously-disjoint components, which is exactly the criterion Kruskal's MST uses to pick edges.
Remarks
This walkthrough used the standard rank-and-compression variant. With nodes and edges, the total work is — practically constant per edge.
A subtle pedagogical point: path compression doesn't fire on every operation. It only fires inside find calls that actually have a non-trivial walk. In edge 4, the find(3) call walked two hops and compressed them. In edge 6, both finds were already one hop deep, so no compression was needed.
For Kruskal's algorithm, the only change is that you'd process edges in weight order rather than insertion order, and you'd record which edges you accepted into the MST.