Disjoint Sets
(Union-Find)

What is a disjoint set?

A collection of non-overlapping (disjoint) sets. Every element belongs to exactly one set at any time. Each set has a designated representative element.

• Partition — a family of disjoint subsets whose union equals the full universe
• Representative — a canonical element that uniquely identifies the set
• Equivalence — two elements are equivalent iff they share the same representative

Formal definition

Given universe U = {x₁, x₂, ..., xₙ}:

• Sets S₁, S₂, ..., Sₖ such that Sᵢ ∩ Sⱼ = ∅ for i ≠ j
• S₁ ∪ S₂ ∪ ... ∪ Sₖ = U

Structure

Each set is a linked list. Every node stores a pointer to the head (representative). Union appends one list to another and updates all head pointers in the shorter list.

Complexity

The problem

Idea

Represent each set as a rooted tree. Each element stores a single parent pointer. The root points to itself and is the representative.

def make_set(x):
    parent[x] = x

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

def union(x, y):
    rx, ry = find(x), find(y)
    if rx != ry:
        parent[ry] = rx

Example

parent[]:  0  0  0  3  3
index:     0  1  2  3  4

Tree 1:    0       Tree 2:  3
          / \                |
         1   2               4

Complexity (naive forest)

Concept

Maintain a rank for each root — an upper bound on the height of its subtree. When merging, attach the shorter tree under the taller one.

def make_set(x):
    parent[x] = x
    rank[x] = 0

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        return
    if rank[rx] < rank[ry]:
        rx, ry = ry, rx
    parent[ry] = rx
    if rank[rx] == rank[ry]:
        rank[rx] += 1

Why it works

• Trees with rank r have at least 2ʳ nodes
• Maximum rank is ⌊log₂ n⌋
• Find is therefore O(log n) worst case

Key property

Track subtree sizes instead of rank

Store the actual count of nodes in each root's subtree. Always attach the smaller tree under the larger root.

def make_set(x):
    parent[x] = x
    size[x] = 1

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        return
    if size[rx] < size[ry]:
        rx, ry = ry, rx
    parent[ry] = rx
    size[rx] += size[ry]

Comparison with union by rank

The idea

During Find(x), make every node on the path from x to the root point directly to the root. Flattens the tree on every query.

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

Complexity

Before and after Find(4)

Before:           After:

     0                 0
     |               / | \
     1              1  2  4
     |              |
     2              3
     |
     3
     |
     4

Path splitting

Every node on the find path points to its grandparent. Single-pass, iterative.

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

Path halving

Every other node on the find path points to its grandparent.

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

Comparison

The optimal combination

• Trees stay shallow (rank bounds height)
• Paths flatten on every Find (compression keeps future Finds fast)
• Rank becomes a stale upper bound after compression, but the algorithm remains correct

Amortised complexity

Practical performance

The Ackermann function

A rapidly growing function defined recursively:

• A(0, j) = j + 1
• A(i, 0) = A(i - 1, 1)   for i > 0
• A(i, j) = A(i - 1, A(i, j - 1))   for i, j > 0

The inverse α(n)

Proof sketch (Tarjan, 1975)

• Assign each non-root node a potential based on how far its rank is from its parent's rank
• Each Find reduces the total potential
• The potential drop per operation is bounded by α(n)

Lower bound

Sedgewick's formulation

A simplified union-find using union by size with a flat array. Popular in algorithms courses (Princeton, Coursera).

public class WeightedQuickUnionUF {
  private int[] parent;
  private int[] sz;
  private int count;

  public WeightedQuickUnionUF(int n) {
    parent = new int[n];
    sz = new int[n];
    count = n;
    for (int i = 0; i < n; i++) {
      parent[i] = i;  sz[i] = 1;
    }
  }

  public int find(int p) {
    while (p != parent[p]) p = parent[p];
    return p;
  }

  public void union(int p, int q) {
    int rP = find(p), rQ = find(q);
    if (rP == rQ) return;
    if (sz[rP] < sz[rQ]) {
      parent[rP] = rQ; sz[rQ] += sz[rP];
    } else {
      parent[rQ] = rP; sz[rP] += sz[rQ];
    }
    count--;
  }
}

Complexity

Motivation

Standard union-find is destructive — path compression and union modify the structure in place. Sometimes we need to query past versions.

Approaches

Conchon-Filliâtre (2007)

A practical persistent union-find using a semi-persistent array (backtrackable). Used in SMT solvers and proof assistants (OCaml).

• Current version: nearly O(α(n)) operations
• Past versions: O(log n) per access with rerooting

Rollback union-find

Support Union and Find as usual, plus Rollback to undo the last Union. Key constraint: do not use path compression (it makes rollback impossible without persistence).

stack = []

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry: return
    if rank[rx] < rank[ry]:
        rx, ry = ry, rx
    stack.append((ry, parent[ry], rank[rx]))
    parent[ry] = rx
    if rank[rx] == rank[ry]:
        rank[rx] += 1

def rollback():
    ry, old_parent, old_rank = stack.pop()
    rx = parent[ry]
    rank[rx] = old_rank
    parent[ry] = old_parent

Offline union-find

When all queries are known in advance, process them in an optimal order (e.g., divide-and-conquer on a timeline). Used in competitive programming for "dynamic connectivity" problems.

Algorithm

1. Sort all edges by weight
2. For each edge (u, v, w) in sorted order:
   — If Find(u) ≠ Find(v), add edge to MST and Union(u, v)
   — Otherwise skip (would create a cycle)
3. Stop when MST has n - 1 edges

Why union-find is ideal

• Need to test connectivity between two nodes efficiently
• Need to merge components as edges are added
• No need to split components
• Exactly the operations disjoint sets provide

Complexity

Static graph

for v in vertices:
    make_set(v)

for (u, v) in edges:
    union(u, v)

# Connected iff find(u) == find(v)

Total: O(V + E · α(V)) — effectively linear.

Dynamic connectivity (incremental)

As edges arrive online, union-find maintains connected components without recomputation. Each new edge triggers at most one Union.

Counting components

Comparison with BFS/DFS

Pixel-level segmentation

Treat each pixel as a node. Connect adjacent pixels whose intensity difference is below a threshold.

for each pixel p:
    make_set(p)

for each adjacent pair (p, q):
    if |intensity(p) - intensity(q)| < T:
        union(p, q)

Performance

• O(n log n) for n pixels (dominated by edge sorting)
• Near-linear in practice with path compression
• Produces perceptually meaningful regions

Felzenszwalb-Huttenlocher (2004)

A graph-based segmentation algorithm using union-find at its core:

The percolation model

An n × n grid of sites, each independently open with probability p. The system percolates if there is a connected path of open sites from top to bottom.

Union-find approach

• Create n² + 2 elements: one per site + virtual top + virtual bottom
• Connect virtual top to all top-row sites
• Connect virtual bottom to all bottom-row sites
• When a site opens, Union with adjacent open sites
• Percolates when Find(top) == Find(bottom)

Monte Carlo simulation

Randomly open sites one at a time. Track when percolation first occurs. Over many trials, estimate the percolation threshold p*.

Why union-find?

Mathematical connection

A disjoint set maintains equivalence classes under a relation that is:

• Reflexive — x ~ x (Make-Set ensures every element is equivalent to itself)
• Symmetric — x ~ y ⇒ y ~ x (Union is symmetric)
• Transitive — x ~ y, y ~ z ⇒ x ~ z (maintained through shared representatives)

Congruence closure

Applications in compilers & type systems

Key takeaways

• The disjoint set ADT supports Make-Set, Find, and Union — a dynamic partition that only merges
• Naive implementations cost O(n) per op; the forest representation is the foundation for all efficient variants
• Union by rank keeps trees shallow — O(log n) worst case
• Path compression flattens trees during Find — combined with rank: O(α(n)) amortised
• α(n) ≤ 4 for all practical n — effectively constant
• Persistent and rollback variants trade O(α(n)) for version access or undo
• Applications: Kruskal's MST, connectivity, percolation, image segmentation, type inference

Recommended reading