Trees & Structures

Union–Find

Track a growing collection of disjoint sets and merge them in nearly constant time — the backbone of connectivity.

Each element points to a parent; arcs go child → parent, and a green node is a set's root. A union (orange) links two roots; a find (blue) walks to the root and flattens the path behind it.

What you're seeing

The disjoint-set structure answers two questions fast: "are these two things in the same group?" and "merge their groups." It keeps each element pointing at a parent; following parents leads to a root that names the whole set. To union two elements, find both roots and point one at the other. To check membership, find both roots and compare. Watch two tricks that keep it fast: union by rank always hangs the shorter tree under the taller, and path compression re-points every node touched on a find straight to the root — so the forest stays almost flat.

The rule

make(x):   parent[x] = x;  rank[x] = 0
find(x):   while parent[x] ≠ x:  x = parent[x]      # walk to root
           (then re-point everything on the path to the root)   # compression
union(a,b):
    ra, rb = find(a), find(b)
    if ra == rb: return                  # already together
    attach the lower-rank root under the higher;  tie ⇒ pick one, rank++

The invariant

The structure maintains a partition of the elements into disjoint sets, and represents each set as a rooted tree. The defining fact: two elements are in the same set if and only if find returns the same root for both. Every operation preserves it — union only ever links two roots (merging exactly the two sets they represent, touching no others), and find never changes which set anything belongs to, only the shape of the tree (path compression re-points nodes to the same root they already had). Because the answer to "same set?" reduces to "same root?", correctness is immediate; the cleverness is all in keeping the trees shallow so find is cheap.

The cost

union / find (amortized) + rank + compressionO(α(n)) rank onlyO(log n)

Union by rank alone keeps every tree height O(log n). Add path compression and a sequence of m operations costs O(m·α(n)) total, where α is the inverse Ackermann function — at most 4 for any number of elements that could ever exist. So each operation is, for all practical purposes, constant time. The bound (Tarjan, 1975) is one of the most surprising in algorithm analysis, and is known to be tight.

In the wild

Union–Find is the connectivity workhorse. It drives Kruskal's minimum-spanning-tree algorithm (add an edge unless its endpoints are already connected), tracks connected components in dynamic graphs and image segmentation, detects cycles while building a graph, powers percolation and maze generation, and unifies type variables in compilers (Hindley–Milner inference) and equivalences in equality-saturation engines. Anywhere you incrementally merge groups and ask "same group?", this is the structure.

Try this

Step through and watch a find: the blue path lights up from a node to its root, then on the next step those nodes all re-point directly to the root — the tree gets visibly shorter. Over a run, no chain ever grows long; that flattening is exactly what buys the near-constant time.

References

  1. Tarjan, R. E. "Efficiency of a Good But Not Linear Set Union Algorithm." Journal of the ACM 22(2):215–225, 1975. The α(n) analysis.
  2. Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §19 (Data Structures for Disjoint Sets). MIT Press, 2022.
  3. Sedgewick & Wayne. Algorithms, 4th ed., §1.5 (Case Study: Union–Find). algs4.cs.princeton.edu/15uf.