Union-Find
Quick reference
| find(i) β with path compression + union by rank | O(Ξ±(n)) β O(1) |
| union(i, j) β with path compression + union by rank | O(Ξ±(n)) β O(1) |
| find(i) β no path compression | O(n) worst case |
| union(i, j) β no union by rank | O(n) worst case |
Imagine a party where people are introduced to each other. Every introduction between two people joins their two friend groups into one bigger group. At any point, someone might ask: "are Alice and Bob in the same friend group?" To answer this by a re-trace of every introduction that ever happened would be slow, and it would become slower as the party continues. Union-find answers it almost immediately instead. Every person keeps a pointer to the current leader of their group. Check whether the leader of Alice and the leader of Bob are the same person, and you have your answer with no re-trace.
This is the whole structure: two operations, find (who is the leader of your group?) and union (merge two groups into one). There is no traversal, no adjacency list, and no visited set, none of the machinery from the last two topics. It answers a narrower question than a general graph does (only "same group or not" and "merge these groups"). But it answers that narrower question much faster than a new DFS/BFS every time someone asks.
The array
structure UnionFind:
parent: array where parent[i] = the parent of i (at the start, every node is its own parent, its own group of one)
rank: array where rank[i] = a rough upper bound on the height of the tree of i (at the start, 0 for everyone)find β follow parent pointers to the root, with path compression
function find(i):
if parent[i] != i:
parent[i] = find(parent[i]) // path compression: point directly at the root
return parent[i]union β merge two roots, with union by rank
function union(i, j):
rootI = find(i)
rootJ = find(j)
if rootI == rootJ:
return // already in the same group: nothing to do
if rank[rootI] < rank[rootJ]:
parent[rootI] = rootJ // attach the shorter tree under the taller tree
elif rank[rootI] > rank[rootJ]:
parent[rootJ] = rootI
else:
parent[rootJ] = rootI // equal rank: pick one, and it grows taller
rank[rootI] += 1With both path compression and union by rank in place, find and union are essentially O(1), technically O(Ξ±(n)), where Ξ± is the inverse Ackermann function. That name sounds difficult, but its meaning in practice is simple: Ξ±(n) grows so slowly that for any number of elements that you could ever have (not only thousands, but numbers far beyond the count of atoms in the observable universe), Ξ±(n) stays 4 or smaller. In plain words: for any real input, this is a constant number of steps. If you drop either optimization, that guarantee is gone.
| Operation | Time | Space | Why |
|---|---|---|---|
| find(i) β with path compression + union by rank | O(Ξ±(n)) β O(1) | O(1) | Amortized over many calls, the tree stays so flat that a walk to the root is, for any practical n, a small constant number of steps. |
| union(i, j) β with path compression + union by rank | O(Ξ±(n)) β O(1) | O(1) | This is two find() calls plus one pointer reassignment, the same near-constant bound as find, because find is the main cost. |
| find(i) β no path compression | O(n) worst case | O(1) | Every call walks the full chain from i to the root again, with nothing flattened after. Repeated unions in the wrong order can leave that chain n nodes long. |
| union(i, j) β no union by rank | O(n) worst case | O(1) | To always attach one specific side (for example, j under i) without a check of tree size can chain n single-node trees onto one growing spine, one union at a time. |
find without path compression
The structure still gives correct answers. The root that it finds is still the right root. What is lost is speed. Every call walks the same chain again from the start instead of a shorter chain for next time. Enough unions chained in the wrong order, and the tree degrades toward the same skewed, linked-list-like shape that a BST degrades into under sorted insertions: a straight line of n nodes, one parent pointer at a time. find becomes O(n).
union without rank (or size)
This is the same failure, with a different cause. If union(i, j) always makes the root of j a child of the root of i, without a check of their sizes, then a sequence like union(1,2), union(1,3), union(1,4), ... keeps stacking single-node trees onto the same growing spine. The height of the tree grows by one with every union instead of staying flat. find still returns correct roots. It just has to walk further and further to get there.
Skipping the 'already same group' check before unioning
This is inefficiency, not a bug, worth telling apart from the two cases above. To run find on both, find that rootI == rootJ, and do nothing wastes a little work. But it produces the exact same structure as if the check caught it early. Compare this to a skip of path compression or rank: those do not crash anything either, but they build up into real O(n) slowdowns as more operations run. This one is only a wasted comparison, one time.
Forgetting to initialize every node as its own parent
find(i) assumes that it can walk parent pointers from the premise that an untouched node is its own root, a group of one, by itself. If you skip the initialization (leave parent[i] at some default such as 0 or undefined), find(i) either walks toward the wrong root or crashes on an undefined lookup, based on the language. Every node needs parent[i] = i set explicitly before you use the structure, even nodes that never end up in any union call.
Sign in to mark problems done β progress syncs across devices.