Disjoint Set (Union–Find)

Overview

A disjoint set (Union–Find) maintains a partition of elements into disjoint components under two operations: FIND(x) returns the component’s representative (root) of x, and UNION(x,y) merges the components containing x and y. With path compression (during FIND) and union by rank/size, both operations run in amortized almost-constant time: $O(\alpha (n))$, where $\alpha$ is the inverse Ackermann function.

Structure Definition

• Universe: elements indexed 0..n-1.
• Arrays:
  • parent[i]: parent pointer; roots satisfy parent[i] = i.
  • rank[i] or size[i]: tie-breaker for unions (rank ≈ upper bound on tree height).
• Invariants: Each set is a rooted tree; paths follow parent pointers up to a root (the representative).

Core Operations

Make-set

function MAKE_SET(n):
    for i in 0..n-1:
        parent[i] = i
        rank[i] = 0        // or size[i] = 1

Find with path compression

function FIND(x):
    if parent[x] != x:
        parent[x] = FIND(parent[x])   // path compression
    return parent[x]

Union by rank (or by size)

function UNION(x, y):
    rx = FIND(x)
    ry = FIND(y)
    if rx == ry: return rx            // already same set
    // attach smaller-rank tree under larger-rank tree
    if rank[rx] < rank[ry]:
        parent[rx] = ry
        return ry
    else if rank[rx] > rank[ry]:
        parent[ry] = rx
        return rx
    else:
        parent[ry] = rx
        rank[rx] = rank[rx] + 1
        return rx

Tip

Rank vs size. Either works. Rank is a theoretical height bound; size is often simpler and competitive in practice (attach smaller to larger).

Example (Stepwise)

Start with elements {0,1,2,3,4,5} as singletons.

1. UNION(0,1) → root 0 with rank 1; sets: {0,1}, {2}, {3}, {4}, {5}.

2. UNION(2,3) → root 2; sets: {0,1}, {2,3}, {4}, {5}.

3. UNION(1,3) → finds FIND(1)=0, FIND(3)=2; ranks equal → attach 2 under 0, increment rank[0]; sets: {0,1,2,3}, {4}, {5}.

4. FIND(3) after prior unions compresses path so parent[3]=0 directly.

Complexity and Performance

• Time (amortized): With path compression + union by rank/size, any sequence of p operations on n elements runs in $O((n+p),\alpha (n))$, which is effectively constant per operation for all practical input sizes.

• Space: O(n) for parent plus rank/size.

Why it’s fast. Path compression flattens find-paths aggressively; union by rank/size prevents tall trees from forming. Together, they limit future costs to the tiny inverse Ackermann factor.

Implementation Details or Trade-offs

• Path compression variants:

  • Full compression (as above) sets every node on the path directly to the root.

  • Path halving / path splitting adjust every other node; often faster in tight loops due to fewer recursive calls.

• Iterative find: Re-implement FIND iteratively to avoid recursion limits; second pass compresses parents to the root.

• ID mapping: If elements aren’t dense integers, map them to 0..n-1 with a dictionary; store original IDs separately.

• Threading: Naïve Union–Find isn’t thread-safe; for parallel Kruskal use coarse-grained locks per root or batched unions (specialized algorithms exist).

Practical Use Cases

• Dynamic connectivity: Maintain connectivity as edges are added in an undirected graph.

• Minimum spanning tree: Kruskal’s algorithm repeatedly unions endpoints of chosen edges. See Kruskal’s Algorithm and Minimum Spanning Trees: Kruskal & Prim.

• Clustering & segmentation: Merge by similarity thresholds (e.g., image components).

• Equivalence closure: Merge constraints expressing “must be equal.”

Limitations / Pitfalls

Warning

Forgetting compression. Union by rank/size alone can still leave long paths after many finds; always combine with path compression.

Warning

Rank updates. Only increase rank when two equal-rank roots are united; otherwise rank is unchanged. Incorrect rank bumps degrade performance.

Warning

Directed graphs. Union–Find models undirected connectivity; for directed reachability, use graph algorithms (e.g., DFS/BFS, SCC).

Summary

Union–Find represents components as parent-pointer forests and achieves near-constant amortized time for connectivity queries by combining path compression with union by rank/size. It is the standard backbone for dynamic connectivity and MST algorithms due to its simplicity, speed, and small memory footprint.

See also

• Kruskal’s Algorithm

• Minimum Spanning Trees: Kruskal & Prim

• Graph Representations