Skip to main content
← CONCEPTS / ALGORITHMS & DATA STRUCTURES
An end-to-end domain learning journey

Disjoint Set Union (Union-Find): Path
Compression & Union by Rank.

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.
Start the journey7 sections
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

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.

Full walkthrough · 7 stages
01
STAGE 01 · CORE INTUITIONfoundation

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.

STAGE 01 · CORE INTUITION

Parent-Pointer Forest Representation

Parent-PointerForest ReIngress / BaselineCore EngineScale ConstraintGuard & VerifyBottleneck SignalProduction OutcomeTarget SLAexposes

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.

02
STAGE 02 · BALANCED MERGINGfoundation

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.

STAGE 02 · BALANCED MERGING

Union by Rank Tree Merge

Union by Rank TreeMergeInput StateCore EngineCore MechanismGuard & VerifyInvariant CheckProduction OutcomeOutput Statetransforms

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.

03
STAGE 03 · TREE FLATTENINGintermediate

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 True
STAGE 03 · TREE FLATTENING

Path Compression Flattening

Path CompressionFlattenValidated InputCore EngineAtomic StepGuard & VerifyError / Retry GuardProduction OutcomeCommitted Resultexecutes

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.

04
STAGE 04 · COMPLEXITY ANALYSISintermediate

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.

STAGE 04 · COMPLEXITY ANALYSIS

Amortized Cost Comparison

Amortized CostComparisoHot PathCore EnginePartition / IndexGuard & VerifyLatency / RAM BoundProduction OutcomeScaled Statebounds

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.

05
STAGE 05 · UNDO & DYNAMIC EDGESadvanced

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.

STAGE 05 · UNDO & DYNAMIC EDGES

DSU Rollback Stack

DSU Rollback StackFault TriggerCore EngineIsolation BoundaryGuard & VerifyFallback / QuarantineProduction OutcomeProtected Pathisolates

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.

06
STAGE 06 · CONCURRENT DSUadvanced

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.

STAGE 06 · CONCURRENT DSU

Lock-Free CAS Union-Find

Lock-Free CASUnion-FindCheckpoint / LogCore EngineReplay / SyncGuard & VerifyConsistency GateProduction OutcomeRecovered Stateverifies

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.

07
STAGE 07 · PRODUCTION PITFALLSadvanced

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.

STAGE 07 · PRODUCTION PITFALLS

DSU Failure Modes & Guards

DSU Failure ModesTelemetry SignalGuardsSLO ThresholdValidation GateCircuit BreakerProduction OutcomeSafe Degradationtrips

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 · Explain the consequences

Practice: Make the trade-off yourself.

Question 1 of 3
Score: 0/3

Why must path compression be disabled when implementing DSU with an O(1) rollback stack?

Recommended Learning Flow