Intermediate · Module 17 · Lesson 7
Union Find
Maintain components with path compression and union by rank.
Lesson 101 of 123
1d streakInteractive Visualization
Trace the algorithm state by state
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Interactive algorithm lab
Union Find
Path compression and union by rank
Components
6
Edge
—
Largest rank
0
Processed
0/5
A
parent
A
rank 0
B
parent
B
rank 0
C
parent
C
rank 0
D
parent
D
rank 0
E
parent
E
rank 0
F
parent
F
rank 0
Why this step happens
Every node starts as the representative of its own component.
Following parent pointers from any node reaches exactly one representative root.
Disjoint Set Union (DSU): Path Compression & Near O(1) Connectivity
Disjoint Set Union (Union-Find) maintains partitions of elements into disjoint subsets. It exposes two core operations: find(p) returns the canonical root representative of element p’s set, and union(p, q) merges the sets containing p and q. By applying Path Compression (flattening trees during find) and Union by Rank (attaching shallower trees beneath deeper trees), the amortized time per operation becomes O(α(N)), where α is the inverse Ackermann function (effectively constant α(N) ≤ 4 for all practical universe sizes).
public class UnionFind {
private final int[] parent;
private final int[] rank;
private int count; // Number of connected components
public UnionFind(int n) {
this.count = n;
this.parent = new int[n];
this.rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
// Find with Path Compression: O(α(N)) amortized
public int find(int p) {
if (parent[p] != p) {
parent[p] = find(parent[p]); // Flatten path directly to root
}
return parent[p];
}
// Union by Rank: Attach smaller tree under larger tree
public boolean union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return false; // Cycle detected: already connected
if (rank[rootP] < rank[rootQ]) {
parent[rootP] = rootQ;
} else if (rank[rootP] > rank[rootQ]) {
parent[rootQ] = rootP;
} else {
parent[rootQ] = rootP;
rank[rootP]++;
}
count--;
return true;
}
public int getCount() { return count; }
}Active Recall Checkpoint
How can Union-Find be used to detect a cycle in an undirected graph during edge addition?
Show answer & explanation
For each edge (u, v), call find(u) and find(v). If find(u) == find(v), u and v already belong to the same connected component; adding this edge creates a cycle. If they differ, call union(u, v) and continue.
Use it when
Use Union-Find for Kruskal’s Minimum Spanning Tree (MST), dynamic connectivity queries, cycle detection in undirected graphs, and image percolation models.
Reconsider when
Union-Find does not naturally support directed graphs or path reconstruction (shortest paths); use BFS/Dijkstra for path distances and Tarjan’s algorithm for directed graph SCCs.
Cost Model
Complexity & Trade-offs
When to use it
- Networks, dependencies, connectivity, shortest paths, and grid movement.
- Ordering prerequisite-constrained work.
- Grouping reachable or mutually reachable states.
Common mistakes
- Marking visited too late and enqueuing the same vertex repeatedly.
- Ignoring disconnected components.
- Using an algorithm whose weight assumptions do not match the graph.
Practice prompts
- Reproduce the worked Union Find example without looking at the trace.
- Change one input condition and explain whether the Union Find invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check