Union-Find (Disjoint Set Union)

Union-Find (Disjoint Set Union / DSU) maintains a collection of disjoint sets with two operations: find(x) returns the representative of x’s set, and union(a, b) merges the sets containing a and b. With two clever optimizations, both run in O(α(n)) — inverse Ackermann time, effectively constant.

The Representation

Each set is a rooted tree. parent[i] points to i’s parent; the root satisfies parent[root] = root and is the set’s representative.

  parent = [0, 0, 0, 3, 3, 5]
  sets:   {0,1,2}  {3,4}  {5}
  0 ← 1           3 ← 4    5
  ↑
  2

find walks up to the root; union hangs one root under the other.

The Two Optimizations

Union by Rank

Keep each tree short by always hanging the smaller tree under the larger (rank = height). This alone bounds tree height at O(log n), because a tree of height h contains at least 2^h nodes.

Path Compression

After find(x), point every node on the path directly at the root. This is what makes DSU nearly O(1): the cost of walking a long path is “paid” once, and the compressed structure makes all future finds on those nodes trivial.

before find(2):  0 ← 1 ← 2
after  find(2):  0 ← 1        (both 1 and 2 point at 0)
                 ↑
                 2

Why O(α(n))?

The two optimizations feed each other: compression only ever happens during finds, and rank bounds how tall trees can grow. The amortized analysis yields the inverse Ackermann function α(n), which grows so slowly that it is ≤ 4 for any n smaller than the number of atoms in the universe. In practice you can treat it as O(1).

Where It Shows Up

  • Kruskal’s algorithm — cycle detection is exactly “do find(u) == find(v) before adding the edge”.
  • Dynamic connectivity — “are a and b connected?” under a stream of edge insertions.
  • Detecting cycles in undirected graphs.
  • Region merging in image segmentation.
  • Equivalence classes — grouping items under a relation.

Practice Trajectory

  1. Implement naive find/union, measure how fast the chain grows with a bad sequence.
  2. Add union by rank — now tree height is bounded.
  3. Add path compression — and watch the “O(1)” happen.
  4. Apply DSU to Kruskal’s algorithm and to a dynamic-connectivity problem set.