Introduction

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.

Try It

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">Each numbered node points to its <b>parent</b>; the root points to itself. <b>Union</b> two nodes to merge their trees (union by rank). <b>Find</b> a node to walk to its root — and watch <b>path compression</b> re-point the whole path straight at the root.</p>
<svg id="forest" viewBox="0 0 480 220" role="img" aria-label="disjoint-set forest"></svg>
<div class="row">
  <label>Union <input id="ua" type="number" min="0" max="7" value="0"></label>
  <label>and <input id="ub" type="number" min="0" max="7" value="1"></label>
  <button id="union" type="button">Union</button>
</div>
<div class="row">
  <label>Find <input id="fx" type="number" min="0" max="7" value="0"></label>
  <button id="find" type="button">Find</button>
  <button id="connected" type="button" class="ghost">Connected?</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status">8 singleton sets. Union some, then Find.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Union-Find (disjoint-set) with UNION BY RANK and PATH COMPRESSION.
// parent[i] = i means i is a root. rank[i] bounds the tree height.
const N = 8;
let parent, rank;
function init(){ parent = [...Array(N).keys()]; rank = Array(N).fill(0); }
init();

// find with full path compression: every node on the path is re-pointed to root.
function find(x){
  const path = [];
  while (parent[x] !== x){ path.push(x); x = parent[x]; }
  for (const p of path) parent[p] = x; // compress
  return { root: x, path };
}
function union(a, b){
  const ra = find(a).root, rb = find(b).root;
  if (ra === rb) return ra;
  // union by rank: hang shorter under taller
  let hi = ra, lo = rb;
  if (rank[ra] < rank[rb]) { hi = rb; lo = ra; }
  parent[lo] = hi;
  if (rank[ra] === rank[rb]) rank[hi]++;
  return hi;
}

// ---- rendering: lay out each tree by depth, roots across the top ----
const SVG = 'http://www.w3.org/2000/svg';
function rootOf(x){ while (parent[x] !== x) x = parent[x]; return x; }
function layout(){
  const children = Array.from({length:N}, () => []);
  const roots = [];
  for (let i=0;i<N;i++){ if (parent[i]===i) roots.push(i); else children[parent[i]].push(i); }
  const pos = {}; let nextX = 0; const COLW = 56, ROWH = 56, OX = 32, OY = 28;
  function place(node, depth){
    const kids = children[node];
    if (kids.length === 0){ pos[node] = { col: nextX++, depth }; return; }
    const cols = kids.map(k => { place(k, depth+1); return pos[k].col; });
    pos[node] = { col: (Math.min(...cols)+Math.max(...cols))/2, depth };
  }
  roots.forEach(r => place(r, 0));
  const xy = {};
  for (let i=0;i<N;i++) xy[i] = { x: OX + pos[i].col*COLW, y: OY + pos[i].depth*ROWH };
  return xy;
}
function render(flashPath){
  const svg = document.getElementById('forest'); svg.innerHTML = '';
  const xy = layout();
  const fp = new Set(flashPath || []);
  // edges first
  for (let i=0;i<N;i++) if (parent[i]!==i){
    const a = xy[i], b = xy[parent[i]];
    const line = document.createElementNS(SVG,'line');
    line.setAttribute('x1',a.x); line.setAttribute('y1',a.y);
    line.setAttribute('x2',b.x); line.setAttribute('y2',b.y);
    line.setAttribute('class','edge'+(fp.has(i)?' flash':''));
    svg.appendChild(line);
  }
  for (let i=0;i<N;i++){
    const g = document.createElementNS(SVG,'g');
    const isRoot = parent[i]===i;
    g.setAttribute('class','node'+(isRoot?' root':'')+(fp.has(i)?' flash':''));
    const c = document.createElementNS(SVG,'circle');
    c.setAttribute('cx',xy[i].x); c.setAttribute('cy',xy[i].y); c.setAttribute('r',15);
    const t = document.createElementNS(SVG,'text');
    t.setAttribute('x',xy[i].x); t.setAttribute('y',xy[i].y); t.textContent = i;
    g.appendChild(c); g.appendChild(t); svg.appendChild(g);
  }
}
function setStatus(t){ document.getElementById('status').textContent = t; }
const val = id => Math.max(0, Math.min(N-1, parseInt(document.getElementById(id).value)||0));

document.getElementById('union').addEventListener('click',()=>{
  const a=val('ua'), b=val('ub');
  if (rootOf(a)===rootOf(b)){ render(); setStatus(fmt('%a% and %b% were already in the same set.', { a: a, b: b })); return; }
  union(a,b); render(); setStatus(fmt('Merged the sets of %a% and %b% (union by rank).', { a: a, b: b }));
});
document.getElementById('find').addEventListener('click',()=>{
  const x=val('fx'); const { root, path } = find(x);
  render([...path, x]);
  setStatus(fmt('find(%x%) = root %root%. Path of %length% node(s) compressed to point straight at %root%.', { x: x, root: root, length: path.length }));
});
document.getElementById('connected').addEventListener('click',()=>{
  const a=val('ua'), b=val('ub'); const same = find(a).root===find(b).root;
  render(); setStatus(fmt('%a% and %b%%v% connected.', { a: a, b: b, v: same?' ARE':' are NOT' }));
});
document.getElementById('reset').addEventListener('click',()=>{ init(); render(); setStatus('Reset: 8 singleton sets.'); });
render();
Result
Console

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.

The Real Complexity

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)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)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⋅α(n))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, α(n)≤4\alpha(n) \le 4. So the cost per operation is, for all practical purposes, a small constant. Tarjan and Fredman–Saks later showed this α(n)\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.

Where It Matters

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

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/union-find/Content licensed under CC BY-NC 4.0.