Disjoint Set Union (DSU) maintains a partition of N elements into non-overlapping sets, supporting find(x) and union(x, y) in O(alpha(N)) amortized time.
TL;DR30-second simplified summary▾
Disjoint Set Union (Union-Find) represents each connected component as a rooted tree stored inside two flat integer arrays: parent[i] and rank[i] (or size[i]). Calling find(x) walks parent pointers upward until reaching the representative root where parent[r] == r, while union(a, b) merges two components by attaching the shorter tree's root beneath the taller tree's root.
Without optimizations, sequential unions can degenerate into a linked list of height O(N), making every find(x) scan linearly. Pairing Union by Rank (which keeps tree height <= floor(log2 N)) with Path Compression (which rewires every visited node along the find path directly to the root) collapses traversal depth on subsequent lookups. Tarjan's amortized analysis proves that m operations across n elements run in O(m * alpha(n)) time, where alpha(n) <= 4 for n <= 10^80.
In production systems, DSU powers Kruskal's minimum spanning tree, incremental network connectivity, compiler alias analysis, and real-time fraud-ring clustering. Its primary limitation is monotonicity: standard DSU supports merges but cannot un-merge edges without either offline rollback stacks (DSU with rollback, O(log N) without path compression) or dynamic link-cut trees.
From patterns to decisions.
Track dynamic connected components in O(alpha(N)) amortized time per operation without rebuilding adjacency lists or running full graph traversals.
Representing Disjoint Sets as Flat Parent-Pointer Trees.
Assume a universe of N elements indexed 0..N-1. Initially every element is its own singleton component: parent[i] = i and rank[i] = 0.
To check whether two nodes belong to the same component, we compare find(a) == find(b). Because each tree has exactly one root (where parent[r] == r), the root ID serves as the canonical component identifier.
Parent-Pointer Forest Representation
1.Stage Objective: Understand how a single parent[] array models dynamic equivalence classes without pointer-heavy graph objects.
2.Level (Foundation): Assume a universe of N elements indexed 0..N-1. Initially every element is its own singleton component: parent[i] = i and rank[i] = 0.
3.Operational Invariant: Each set is a rooted tree stored in a contiguous parent[] array, enabling cache-friendly upward traversal.
Caption: Each set is a rooted tree stored in a contiguous parent[] array, enabling cache-friendly upward traversal.
Preventing Degenerate Chains with Union by Rank & Size.
When merging roots ra and rb (ra != rb), attaching ra under rb blindly can create a linear chain of depth N. Union by Rank compares rank[ra] and rank[rb], attaching the smaller-rank root under the larger-rank root and incrementing rank only on ties.
Union by Size tracks component cardinality in size[root] (often stored as negative values inside parent[root] to halve memory footprint) and always attaches the smaller component to the larger one.
Union by Rank Tree Merge
1.Stage Objective: Bound worst-case tree depth to O(log N) by always attaching the shallower tree under the deeper tree.
2.Level (Foundation): When merging roots ra and rb (ra != rb), attaching ra under rb blindly can create a linear chain of depth N. Union by Rank compares rank[ra]
3.Operational Invariant: Attaching a rank-1 tree under a rank-2 tree keeps the resulting tree rank unchanged at 2.
Caption: Attaching a rank-1 tree under a rank-2 tree keeps the resulting tree rank unchanged at 2.
Collapsing Lookup Paths with Recursive & Iterative Path Compression.
During find(x), every node on the path from x to root r belongs to the same set. Full path compression sets parent[node] = r for every node on that path; iterative path halving (parent[x] = parent[parent[x]]) achieves the same O(alpha(N)) amortized bound in a tight non-recursive loop with zero stack-overflow risk.
class DisjointSet:
def __init__(self, n: int) -> None:
if n < 0:
raise ValueError('Element count must be non-negative')
self.parent = list(range(n))
self.rank = [0] * n
self.components = n
def find(self, x: int) -> int:
if not (0 <= x < len(self.parent)):
raise IndexError(f'Node {x} out of bounds')
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, a: int, b: int) -> bool:
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
self.components -= 1
return TruePath Compression Flattening
1.Stage Objective: Eliminate repeated long traversals by rewiring visited nodes directly to the component root.
2.Level (Intermediate): During find(x), every node on the path from x to root r belongs to the same set. Full path compression sets parent[node] = r for every node
3.Operational Invariant: Path compression and path halving collapse multi-hop chains directly toward the representative root.
Caption: Path compression and path halving collapse multi-hop chains directly toward the representative root.
Why O(alpha(N)) Is Effectively Constant Time in Practice.
Assuming both Path Compression and Union by Rank are enabled, a sequence of M operations on N elements takes O(M * alpha(N)) time, where alpha(N) is the inverse Ackermann function. For N <= 2^65536 (far exceeding atoms in the observable universe), alpha(N) <= 4.
Memory overhead is strictly 8 bytes per element (two 32-bit ints) or 4 bytes per element using negative-size encoding in a single int32 array.
Amortized Cost Comparison
1.Stage Objective: Distinguish worst-case single-operation bounds from amortized inverse-Ackermann complexity.
2.Level (Intermediate): Assuming both Path Compression and Union by Rank are enabled, a sequence of M operations on N elements takes O(M * alpha(N)) time, where alp
3.Operational Invariant: Combining both heuristics drops amortized cost per operation from O(log N) down to O(alpha(N)) <= 4.
Caption: Combining both heuristics drops amortized cost per operation from O(log N) down to O(alpha(N)) <= 4.
DSU with Rollback for Offline Edge Deletions.
Path compression mutates parent pointers destructively, making undo impossible. When you need rollback (e.g., offline dynamic connectivity with a segment tree over time), omit path compression and keep Union by Rank/Size alone (O(log N) per op).
Push (rb, prev_parent_rb, ra, prev_rank_ra) onto an undo stack on every union so rollback() restores exact prior state in O(1) time per undone merge.
DSU Rollback Stack
1.Stage Objective: Support undoable unions when algorithms need backtracking or sliding-window edge deletions.
2.Level (Advanced): Path compression mutates parent pointers destructively, making undo impossible. When you need rollback (e.g., offline dynamic connectivity w
3.Operational Invariant: Recording modified (child, old_parent, root, old_rank) tuples enables deterministic O(1) rollback.
Caption: Recording modified (child, old_parent, root, old_rank) tuples enables deterministic O(1) rollback.
Wait-Free & Sharded Union-Find Under Multi-Threaded Workloads.
In multi-core graph analytics (assuming 64-bit atomic CAS), Wait-Free Union-Find (Anderson & Woll) encodes (parent, rank) into a single 64-bit word and uses compare_exchange_weak so find() performs CAS-based path halving without locks.
For distributed or high-contention services, partition components or batch edges per shard before merging.
Lock-Free CAS Union-Find
1.Stage Objective: Avoid coarse mutexes when multiple threads merge and query a shared graph.
2.Level (Advanced): In multi-core graph analytics (assuming 64-bit atomic CAS), Wait-Free Union-Find (Anderson & Woll) encodes `(parent, rank)` into a single 64
3.Operational Invariant: Packing parent and rank into one 64-bit atomic word enables lock-free path halving and merges.
Caption: Packing parent and rank into one 64-bit atomic word enables lock-free path halving and merges.
When Not to Use Standard DSU: Deletions, Recursion & Dynamic IDs.
Three classic production bugs hit DSU deployments: (1) recursive find() overflowing the call stack on 10^6-node unflattened inputs—always use iterative path compression or path halving; (2) assuming DSU handles arbitrary edge deletions online—use Link-Cut Trees or offline segment-tree-over-time rollback; (3) unbounded string-to-int mapping tables leaking memory without LRU eviction or epoch compaction.
DSU Failure Modes & Guards
1.Stage Objective: Recognize when DSU breaks down and how to guard against stack overflows and non-integer keys.
2.Level (Advanced): Three classic production bugs hit DSU deployments: (1) recursive `find()` overflowing the call stack on 10^6-node unflattened inputs—always
3.Operational Invariant: Iterative path halving, bounds validation, and epoch compaction prevent stack overflows and leaks.
Caption: Iterative path halving, bounds validation, and epoch compaction prevent stack overflows and leaks.
Practice: Make the trade-off yourself.
Why must path compression be disabled when implementing DSU with an O(1) rollback stack?