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))? A Proof Sketch

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).

The intuition behind the bound is a rank ladder. Define a rank-1 set as a tree of height ≥ 1 (i.e., at least two nodes); a rank-2 set as a tree whose every child subtree has rank ≥ 1; and so on. Union by rank ensures a tree of rank k contains at least 2^k nodes, so ranks stay ≤ log₂(n). Path compression then guarantees that once a node climbs one rung of the ladder, the path that got it there is flattened and can’t be climbed again — each node pays at most one visit per ladder level. The number of ladder levels that matter is α(n), and the total work over any sequence of m operations is O((m + n) · α(n)). Because α(n) ≤ 4 for every n you will ever encounter, this is “effectively O(1)” — but it is a different constant from O(1), and amortized rather than per-operation.

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.

Beyond the Basics

DSU is more versatile than its reputation suggests:

• Offline queries — answer “how many distinct values are in [l, r]?” or “weighted number of components after edge deletions” by reversing time: process deletions as insertions, unioning components as edges return.
• Union-find on trees / grids — index 2D grid cells as r * cols + c and union adjacent cells to build connected components of a bitmap (region labeling) in nearly linear time.
• Weighted / maximum spanning tree — the same find/union used by Kruskal’s directly solves MST and minimum-bottleneck problems; adding a component-size field lets DSU also track component sizes for offline LCA (“union-find tree” / Kruskal reconstruction tree) tricks.

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.
5. Solve a grid-connected-components problem by mapping cells to flat indices and unioning neighbors.
6. Solve an offline “edges after deletions” problem by running the process in reverse.