Two heuristics, three lines each, that take a structure from linear to effectively constant — and produce the strangest running time in the book.
A disjoint-set structure maintains a collection of non-overlapping sets under two operations: merge two sets, and ask which set an element belongs to. It is a small interface with an outsized payoff, because the analysis is the most surprising in CLRS. A naive implementation is O(n) per operation. Add union by rank and path compression — six lines of code between them — and the amortized cost falls to O(α(n)), where α is the inverse Ackermann function and is at most 4 for any n that could be written down in this universe.
S = {S₁, S₂, …, Sₖ} of disjoint dynamic sets. Each set is identified by a representative, some member of it. Which member is the representative does not matter, only that it stays the same as long as the set is unchanged.| Operation | Meaning |
|---|---|
MAKE-SET(x) | Create a new set whose only member, and representative, is x. Requires x not already in another set. |
UNION(x, y) | Merge the two sets containing x and y into one, and destroy the originals. |
FIND-SET(x) | Return a pointer to the representative of the set containing x. |
Throughout, n is the number of MAKE-SET operations and m is the total number of operations. Since the sets are disjoint, each UNION reduces the set count by one, so there are at most n - 1 unions.
The motivating use is deciding, for an undirected graph, whether two vertices are connected.
CONNECTED-COMPONENTS(G)
1 for each vertex v ∈ G.V
2 MAKE-SET(v)
3 for each edge (u, v) ∈ G.E
4 if FIND-SET(u) ≠ FIND-SET(v)
5 UNION(u, v)
SAME-COMPONENT(u, v)
1 return FIND-SET(u) == FIND-SET(v)Each vertex starts alone; each edge merges the two endpoints’ components. After processing every edge, two vertices are connected exactly when they share a representative.
O(V + E). Disjoint sets win when the graph is dynamic — edges arriving over time with connectivity queries interleaved — because DFS would have to rerun from scratch after every edge. This is also the exact structure Kruskal’s algorithm in Chapter 21 uses to detect whether an edge would form a cycle.The first attempt: each set is a linked list. The list head is the representative, and every object points back to it.
MAKE-SET: create a one-element list. O(1).FIND-SET: follow the back pointer. O(1).UNION: append one list to the other — but every object in the appended list needs its back pointer updated. O(length).n MAKE-SETs, then union the sets one at a time always appending the larger list onto the smaller. The ith union updates i pointers, so n-1 unions cost Θ(n²) — amortized Θ(n) per operation.lg n times, and a sequence of m operations costs O(m + n lg n).The doubling argument here is worth internalising on its own — the same “merge the smaller into the larger” trick gives good bounds in many other settings.
The faster representation abandons lists for trees. Each set is a rooted tree, each node points only to its parent, and the root is the representative and points to itself.
MAKE-SET(x) FIND-SET(x) UNION(x, y)
1 x.p = x 1 if x ≠ x.p 1 LINK(FIND-SET(x),
2 x.rank = 0 2 return FIND-SET(x.p) FIND-SET(y))
3 return x.pn nodes, making FIND-SET cost Θ(n). The representation only pays off once both heuristics are applied.rank is an upper bound on the node’s height. On a tie, pick either and increment the winner’s rank by one.LINK(x, y)
1 if x.rank > y.rank
2 y.p = x
3 else
4 x.p = y
5 if x.rank == y.rank
6 y.rank = y.rank + 1 // only case where a rank growsThis is the tree analogue of the weighted-union heuristic: hang the shallower tree under the deeper one so the result does not get taller. Union by rank alone gives O(m lg n).
FIND-SET, after finding the root, make every node on the path point directly to the root. It costs nothing extra asymptotically — the path was walked anyway — and it flattens the tree permanently for all future queries.FIND-SET(x) // with path compression
1 if x ≠ x.p
2 x.p = FIND-SET(x.p) // two-pass: recurse, then re-point
3 return x.pThree lines. The recursion walks up to the root; the assignment on the way back down re-parents every node visited.
m MAKE-SET, UNION, and FIND-SET operations, n of which are MAKE-SET, can be performed on a disjoint-set forest with union by rank and path compression in worst-case time O(m · α(n)).| Heuristics used | Total for m operations |
|---|---|
| Neither | O(m n) |
| Union by rank only | O(m lg n) |
| Path compression only | Θ(n + f·(1 + log2+f/n n)) |
| Both | O(m · α(n)) |
α(n) is the inverse of the Ackermann function, which grows so explosively that its inverse grows more slowly than any function you are likely to name — slower than lg n, slower than lg* n, slower than lg lg lg n.
n in range | α(n) |
|---|---|
| 0 to 2 | 0 |
| 3 | 1 |
| 4 to 7 | 2 |
| 8 to 2047 | 3 |
2048 to A₄(1), a number far exceeding the atoms in the observable universe | 4 |
α(n) ≤ 4 and the operations are constant time. CLRS is careful to say the bound is not constant — α(n) does grow without bound, just unimaginably slowly — but no input you will ever run on can push it past 4. Tarjan later proved Θ(m α(n)) is also a lower bound for this problem, so the analysis is tight and cannot be improved.α(n), and proving that is one of the hardest analyses in the book — CLRS devotes a full section to it using a potential function in the style of Chapter 16.MAKE-SET, UNION, FIND-SET. Each set has an arbitrary but stable representative.FIND-SET returns the same representative. Kruskal’s algorithm depends on it.O(m + n lg n), because each element’s set doubles whenever its pointer is updated.FIND-SET, re-point every node on the path directly to the root. Three lines, and free — the path was traversed anyway.O(m · α(n)), where α(n) ≤ 4 for any conceivable input. Either heuristic alone gives only a logarithmic bound.Part V is complete, and with it every data structure in the book. Part VI turns to graphs. Chapter 20 covers the representations — adjacency lists and matrices — and the two traversals, breadth-first and depth-first search, that every later graph algorithm is built from, along with topological sort and strongly connected components.