Union-Find

Imagine a room full of strangers. Now and then two of them shake hands and merge their circles of friends into one. At any moment you might be asked: are these two people in the same circle? As the handshakes pile up, answering that quickly stops being obvious.

Union-Find — also called the disjoint-set structure — does exactly this. It supports two operations: union, which merges the groups of two elements, and find, which returns a representative for an element's group so you can test whether two elements are connected.

The astonishing part is the speed. With two small tricks — union by rank and path compression — each operation costs, in practice, less than a constant: for any input you could ever build, the amortized cost per operation is smaller than five. This is not a hard open problem; it is a solved one, and its solution is one of the most beautiful results in algorithm analysis.

Each element starts as its own tiny tree, pointing only to itself. Union two elements to merge their trees; Find an element to follow the parent pointers up to its root. Watch what happens to the arrows after a find.

<p class="hint">{{hint}}</p>
<svg id="forest" viewBox="0 0 480 220" role="img" aria-label="{{aria_forest}}"></svg>
<div class="row">
  <label>{{lbl_union_a}} <input id="ua" type="number" min="0" max="7" value="0"></label>
  <label>{{lbl_union_b}} <input id="ub" type="number" min="0" max="7" value="1"></label>
  <button id="union" type="button">{{btn_union}}</button>
</div>
<div class="row">
  <label>{{lbl_find}} <input id="fx" type="number" min="0" max="7" value="0"></label>
  <button id="find" type="button">{{btn_find}}</button>
  <button id="connected" type="button" class="ghost">{{btn_connected}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="status" id="status">{{status_init}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#forest { width: 100%; height: auto; background: #f5f8fb; border: 1px solid #d6e0ea; border-radius: 10px; }
.node circle { fill: #e8eef3; stroke: #1d3557; stroke-width: 2; }
.node.root circle { fill: #1d3557; }
.node.flash circle { fill: #e63946; stroke: #c92f3c; }
.node text { font: 700 13px ui-monospace, monospace; fill: #1d3557; text-anchor: middle; dominant-baseline: central; }
.node.root text, .node.flash text { fill: #fff; }
.edge { stroke: #9fb2c8; stroke-width: 2; fill: none; }
.edge.flash { stroke: #e63946; stroke-width: 3; }
.row { display: flex; gap: .5rem; align-items: center; flex-wrap: wrap; margin: .5rem 0 0; }
label { font-size: .9rem; color: #333; }
input { width: 3rem; font: 600 14px system-ui; padding: .2rem .3rem; border: 1px solid #adb1b8; border-radius: 6px; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .8rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; margin: .6rem 0 0; min-height: 1.3em; color: #0a3d62; }

// Code not found

Notice the magic of path compression: the first time you find a deep element, every node on the path is re-pointed straight at the root. The next query on any of them is one hop. Combined with union by rank — always hanging the shorter tree under the taller one — the forest stays almost perfectly flat, which is why connectivity questions answer in near-constant time.

How fast is Union-Find, really?

• Naively, a find can walk a long chain of parent pointers, so a single operation could cost $O(n)$ in a bad tree.
• Union by rank keeps the trees shallow by always attaching the smaller tree under the larger, bounding height at $O(\log n)$.
• Path compression then re-points every node it visits straight to the root, so repeated queries get cheaper over time.
• Together they are nearly constant. In 1975 Robert Tarjan proved that a sequence of m operations on n elements runs in $O(m \cdot \alpha(n))$ time, where $\alpha$ is the inverse Ackermann function.

The function $\alpha$ grows so slowly that for any number of elements that could fit in the observable universe, $\alpha(n) \le 4$. So the cost per operation is, for all practical purposes, a small constant. Tarjan and Fredman–Saks later showed this $\alpha(n)$ bound is optimal — no pointer-machine structure can do asymptotically better. Unlike P vs NP, this is not an open question: Union-Find is a solved problem, with a matching lower bound to prove we cannot improve it.

"Keep track of what's connected as connections are added" is a shape that shows up everywhere, and Union-Find is its workhorse:

• Minimum spanning trees: Kruskal's algorithm uses Union-Find to add the cheapest edge whenever it joins two not-yet-connected components. See the minimum spanning tree article.
• Network and grid connectivity: testing whether two computers, pixels, or cells belong to the same component, including percolation models in physics.
• Image segmentation: merging adjacent pixels with similar color into regions.
• Compilers and type inference: unification merges equivalence classes of variables and types.

Wherever components grow by merging and you must answer "same group?" instantly, Union-Find is almost always the right tool. It also pairs naturally with graph problems like graph coloring where connected structure matters.

Union-Find is a rare kind of victory in computer science: a problem so completely solved that we have both an algorithm running in near-constant time and a matching proof that no one can do meaningfully better. Union by rank keeps the trees short, path compression flattens them as you go, and the inverse Ackermann function quietly absorbs whatever is left.

So the next time you merge two groups and ask whether two things are connected, remember that the answer comes back in less time than it takes to read the question — and that, unlike so many problems in this collection, this one has a happy ending we can prove.