Disjoint Set Union (DSU)

Definition: A data structure (also called Union-Find) that tracks a partition of a set into disjoint subsets, supporting efficient Find and Union operations.

How It Works

Each element starts as its own subset, represented as a forest where every node points to a parent, and a root points to itself. Two operations drive everything:

Find(x): walk parent pointers up from x until reaching a node that is its own parent (the root), which identifies which subset x belongs to.
Union(x, y): merge the subsets containing x and y by attaching one root under the other.

find(x):
    while parent[x] != x:
        x = parent[x]
    return x

union(x, y):
    root_x, root_y = find(x), find(y)
    if root_x != root_y:
        parent[root_x] = root_y

Two optimizations turn this from a potentially slow structure into a near-constant-time one:

Path Compression: during Find, after locating the root, re-point every node visited along the way directly to that root. Future Find calls on those nodes become O(1) instead of retracing the same chain.
Union by Rank/Size: always attach the smaller (or shallower) tree’s root under the larger one’s root, rather than picking arbitrarily. This keeps trees from growing needlessly tall.

Path compression alone gives O(log n) amortized per operation. Combining it with union by rank/size pushes the bound down to O(α(n)), where α is the inverse Ackermann function, a function that grows so slowly it’s effectively at most 4 for any input size that could ever be represented in physical memory.

Complexity Analysis

Operation	With Path Compression + Union by Rank	Without optimizations
Find	O(α(n)) amortized, effectively O(1)	O(n) worst case (degenerate chain)
Union	O(α(n)) amortized	O(n) worst case
Space	O(n)	O(n)

α(n), the inverse Ackermann function, is so slow-growing that it’s treated as a constant in essentially all practical engineering contexts.

Why It Matters

Essential for Kruskal’s minimum spanning tree algorithm, where edges are processed in ascending weight order and DSU rejects any edge that would connect two nodes already in the same component, since that edge would only create a cycle.
Powers network connectivity checks and dynamic (online) graph cycle detection, where edges are added incrementally and “are these two nodes connected” must be answered after each addition, without recomputing connectivity from scratch every time.
Used in image processing for connected-component labeling of pixels, and in compiler alias analysis, wherever “are these two things ultimately the same group” needs to be answered repeatedly and cheaply.

Common Pitfalls

Forgetting Path Compression or Union by Rank/Size individually still works correctly, but omitting both causes the tree to degenerate into a linear chain, degrading Find to O(n) per call in the worst case.
Implementing Union by always attaching x’s root under y’s root regardless of subtree size defeats the purpose of Union by Size/Rank and reintroduces the long-chain problem it was meant to solve.
Confusing “same component” with “adjacent”; DSU only answers reachability/grouping questions, not shortest-path distance or direct-edge existence between two nodes.
Applying DSU to problems requiring the ability to split a set back apart; DSU is fundamentally an incremental-merge-only structure with no efficient Split operation, since the path-compression optimization actively destroys the historical structure needed to undo a merge.
Forgetting to path-compress on Find (only doing union by rank) still passes correctness tests but silently loses most of the performance benefit under heavy Find-only workloads.

Comparison

	DSU	BFS/DFS connectivity check	Adjacency-list graph + rebuild
Query “are x, y connected”	O(α(n)) amortized	O(V + E) per query	O(V + E) per query
Incremental edge additions	O(α(n)) per union	Requires re-traversal	Requires re-traversal
Supports edge removal	No	Yes, naturally	Yes, naturally
Typical use	Kruskal’s MST, online connectivity	One-off connectivity checks	Static graph analysis

Example

Tracking connected components in a social network as new friend connections form over time:

parent = [0,1,2,3,4]         # 5 people, each their own component
union(0,1) -> parent[find(1)] = find(0)   # 0 and 1 now connected
union(2,3) -> parent[find(3)] = find(2)   # 2 and 3 now connected
find(1) == find(0)  -> True   # same friend group
find(1) == find(2)  -> False  # different friend group
union(1,2)          # merges the two friend groups into one
find(0) == find(3)  -> True   # now transitively connected

In Kruskal’s algorithm, this same structure decides MST edges: given edges sorted by weight, an edge is added to the spanning tree only if find(u) != find(v), after which union(u, v) merges the two components, guaranteeing the final structure is cycle-free by construction.

Path Compression, Visually

Before compression, find(4) might have to walk a long chain:

1 <- 2 <- 3 <- 4     find(4): 4 -> 3 -> 2 -> 1 (3 hops)

After find(4) completes, path compression re-points every node visited directly to the root:

1 <- 2, 1 <- 3, 1 <- 4     find(4) again: 4 -> 1 (1 hop)

This is why a sequence of Find calls gets dramatically cheaper over time even without any explicit “rebalance” step; the tree flattens itself as a side effect of normal use.

Union by Rank, Traced

Starting from 6 singleton elements, each with rank=0, applying a sequence of unions:

init:            parent=[0,1,2,3,4,5]  rank=[0,0,0,0,0,0]

union(0,1): ranks equal (0,0) -> attach 1 under 0, bump 0's rank
            parent=[0,0,2,3,4,5]  rank=[1,0,0,0,0,0]

union(2,3): ranks equal (0,0) -> attach 3 under 2, bump 2's rank
            parent=[0,0,2,2,4,5]  rank=[1,0,1,0,0,0]

union(0,2): ranks equal (1,1) -> attach 2 under 0, bump 0's rank
            parent=[0,0,0,2,4,5]  rank=[2,0,1,0,0,0]

union(4,0): ranks differ (0 vs 2) -> attach the lower-rank root (4) under the higher-rank root (0), rank unchanged
            parent=[0,0,0,2,0,5]  rank=[2,0,1,0,0,0]

Rank only increments when two trees of equal rank merge; attaching a shorter tree under a taller one never needs to bump the taller tree’s rank, since the taller tree’s height already dominates. This is precisely what keeps the forest shallow without ever needing full rebalancing.

FAQ

Can DSU tell you the size of a component? Not by default, but it’s a one-line addition: track a size[] array alongside parent[], updating it during union by adding the smaller component’s size into the larger one’s root.

Is DSU a tree data structure like a BST? Structurally yes, it’s a forest of trees connected by parent pointers, but it has none of the ordering or search properties of a BST. Its only supported queries are “who’s your root” and “merge these two roots.”

Variants

Union by rank vs. union by size: rank tracks an upper bound on tree height, size tracks element count. Both give the same O(α(n)) amortized bound; size is often preferred in practice because it doubles as a directly useful “how big is this component” query.
Weighted Quick-Union: the historical name (predating “union by size/rank” terminology) for attaching the smaller tree under the larger one, without path compression. Path compression is a separate, complementary optimization that can be added on top.
Persistent/rollback DSU: a variant that logs union operations so they can be undone, used in offline algorithms that need to process queries in a different order than the unions were given, at the cost of skipping path compression (which is irreversible) in favor of union by rank alone.

Real-World Systems

Compilers use DSU-style union-find in type inference (Hindley-Milner style) to track which type variables have been unified with each other during type checking.
Image editing and computer vision libraries use DSU for connected-component labeling, grouping adjacent same-colored or same-valued pixels into a single labeled region in close to linear time.
Network provisioning and infrastructure tools use DSU-like connectivity tracking to answer “are these two nodes on the same network segment” as links are added incrementally, without recomputing full graph connectivity from scratch.

Referenced by

Dig deeper

Spot an error in this note?