Union–Find — every question, written out
Disjoint sets with near-constant merge and lookup. Process edges once and components, cycles and connectivity all fall out. Path compression does the magic.
Read the union–find explanation and watch it run
What does "α(n) amortized" actually promise, and what must be true to claim it?
Complexity derivation
Below 5 for any real n, averaged over a sequence — and it needs both path compression and union by rank
The inverse Ackermann function grows so slowly that it is at most 4 for any n that could be stored, so "effectively constant" is a theorem rather than hand-waving. But it is amortized over a sequence of operations, and Tarjan’s proof requires both heuristics — compression to flatten what it walks, and a union rule that keeps trees shallow in the first place. Saying α honestly and then saying "constant in practice", in that order, is what an interviewer is listening for.
Prism’s `find` halves paths, but its union is `parent[ra] = rb` with no rank check. What bound does that earn?
Complexity derivation
Amortized O(log n) per operation — compression alone is not enough for the α bound
Each heuristic on its own gives amortized O(log n); together they give α(n). This implementation has only the compression half, so O(log n) is the honest claim for what the visualization runs — and for the graph sizes it draws, the difference is invisible anyway. Adding union by size would be two extra lines, and the deck names the bound rather than borrowing a stronger one.
A single BFS finds all components in O(V + E). When is union–find worth the extra structure?
Complexity derivation
When edges arrive over time and queries interleave, so there is no single graph to traverse
On a static, fully known graph, one traversal answers the question with less machinery, and reaching for a disjoint-set structure there is over-engineering. What union–find buys is the *online* case: merges and "same group?" queries interleaved, with no opportunity to re-traverse between them. That is also why it sits inside Kruskal, where edges arrive in sorted order by design.
What single property makes every union–find operation correct?
Invariant identification
Two nodes share a set exactly when their parent chains end at the same root
Everything else — compression, union by rank, size bookkeeping — exists to make the walk shorter while preserving that one equivalence. Its operational corollary catches most bugs: only roots may be compared and only roots may be merged, so `parent[find(x)] = find(y)` is correct and `parent[x] = y` silently splits a set. Prism labels each node with its current root index, which makes the invariant something you can read off the drawing.
See it run — Every badge is one of two values — the two roots — so the labels are exactly the component map.
Why does a successful union always reduce the component count by exactly one?
Invariant identification
It joins two distinct sets into one, and two-into-one is a decrease of exactly one, whatever their sizes
A union takes two disjoint sets and produces one, so the tally drops by one no matter whether the sets held two nodes or two million. That arithmetic gives a free result worth remembering: n nodes reach k components after exactly n − k successful unions, and every rejected edge is pure cycle content. It is also the sanity check for a Kruskal implementation, which must stop after exactly n − 1 unions.
See it run — The final union takes the count from 3 to 2 — one step, however large the two blobs were.
The trace reports find(A) = L and find(L) = L for the edge A — L. What does the algorithm do, and why?
Trace prediction
It rejects the edge — the shared root proves a path already exists, so this one closes a cycle
Equal roots mean the two endpoints are already in the same set, so a route between them exists and this edge can only complete a loop. The count is untouched and the edge is marked rejected. This two-line comparison is the entire cycle test inside Kruskal’s algorithm — no traversal, no visited set, just "same root or not".
See it run — The rejection reason names the shared root; the edge is drawn struck through rather than as a tree edge.
As the run proceeds, find(E) answers E, then F, then G, then I. Is something wrong?
Trace prediction
No — a root becomes an internal node when its set is merged under another, so root identity is not stable
The root is only a representative, chosen by whichever union happened most recently — it carries no meaning beyond "everyone in this set walks here". When E’s set is merged under another, yesterday’s root becomes an ordinary internal node and every member’s chain simply continues one hop further. Caching a root across unions is therefore a stale-pointer bug in disguise, and comparing two live `find` results is the only safe query.
See it run — find(E) now answers I — its third change of root, and E’s own parent pointer explains none of it.
A correct `find` without compression passes every test and times out in production. Why?
Code diagnosis
Unions can build a chain, and every `find` then walks its full length — O(n) per query
Merging without compression leaves the walk length free to grow, and a sequence like union(1,2), union(2,3), union(3,4) builds a path with no branching at all. Every later query then traverses it end to end, so a structure advertised as near-constant behaves linearly. The fix is one line inside the walk, and its absence is the most common disjoint-set performance bug precisely because correctness is unaffected.
A union is written `parent[a] = b` instead of `parent[find(a)] = find(b)`. What breaks?
Code diagnosis
A’s old set is torn in two — everything that pointed at A’s root stays behind, unmerged
Pointing a non-root at another node re-routes only that node and whatever hangs beneath it, leaving the rest of its former set attached to the old root. Two nodes that should now be equivalent walk to different roots, so the query answers no. The invariant states it directly — only roots may be merged — and the count keeps decrementing regardless, so nothing complains.
Prism processes edges in input order. What single change turns this run into Kruskal’s algorithm?
Comparison
Sort the edges by weight first; the accept-or-reject test is already exactly right
Kruskal is exactly this loop with the edges visited in non-decreasing weight order: take each edge unless its endpoints already share a root. The cycle test needs no modification because "already connected" means the same thing whatever order edges arrive in. That is why the disjoint-set structure is usually taught alongside Kruskal — the greedy proof supplies the sort, and union–find supplies everything else.
You must answer "are X and Y connected?" a million times on a graph that never changes. Which structure?
Comparison
One traversal labelling every node with a component id; each query is then a single comparison
One BFS or DFS pass writes a component id into an array, after which "connected?" is `id[x] === id[y]` — a plain comparison with no walk at all. Union–find is the answer to a different question, where edges keep arriving and there is no static graph to preprocess. Recognising which of the two regimes you are in is the actual skill; reaching for the fancier structure by reflex is the mistake.
The problem now removes edges as well as adding them. Can union–find handle it?
Edge case reasoning
Not directly — the structure only coarsens; splitting a set needs offline processing or a different structure
A union merges two trees irreversibly, and path compression then rewrites pointers throughout, so there is no record of which nodes belonged where. The standard answers are offline — process the timeline backwards so deletions become insertions — or a rollback DSU that forgoes compression and keeps a stack of overwritten pointers, or a link-cut tree for the fully dynamic case. Interviewers keep this follow-up loaded precisely because "just undo it" is the tempting wrong answer.
The edge stream contains a duplicate of an edge already processed. What happens?
Edge case reasoning
Both roots already match, so it is rejected as a cycle and the count is unchanged
A repeated edge, a self-loop, and a genuine cycle-closing edge are all the same event to this structure: `find` on both ends returns the same root. That is a useful robustness property, since real edge streams are rarely deduplicated. It also means the rejection count measures redundancy in the input rather than anything about the algorithm.
Fourteen nodes, thirteen edges, one rejection. How many components remain, without looking at the graph?
Edge case reasoning
Two — twelve successful unions each dropped the count by one, from fourteen
Start at n components, subtract one per successful union, ignore rejections entirely: 14 − 12 = 2. Nothing about the graph’s shape enters the calculation, which is what makes the running counter trustworthy rather than a heuristic. Prism’s default run is exactly this case, and its summary confirms two components remain.
See it run — The thirteenth edge H — N is rejected, leaving twelve unions and therefore two components.
What does union by size buy that path compression does not, given both are one line?
Trade-off & selection
It stops deep trees forming at all, whereas compression only repairs them once something walks them
The two heuristics attack the same problem from opposite ends: union by size prevents a shallow tree being buried under a deep one, while compression flattens whatever chain a `find` happens to traverse. Prevention matters because a query that never runs never repairs anything, so a workload heavy on unions and light on finds benefits mostly from the rank rule. Together they give α(n), and the size array also answers "how big is X’s group?" for free.
Your nodes are email addresses rather than integers. Keep a hash map as the parent structure, or intern to indices?
Trade-off & selection
Intern to indices first — an array-backed structure is measurably faster and no less clear
Union–find is one of the fastest structures in existence precisely because it is two integer arrays with excellent cache behaviour, and a hash map on the hot path throws that away. Build a dictionary from key to index once as the input arrives, run the structure over indices, and translate back only for output. The accounts-merge family of problems is exactly this shape, and the interning step is the part candidates forget.
Explain union–find to someone who has never programmed. Say it out loud before revealing.
Explain it plainly
Picture a world of companies, each with a chief executive. Ask any employee "who is ultimately in charge of you?" and they walk up their reporting line until they reach someone who reports to nobody — that person is the answer. Two employees work for the same company exactly when that walk ends at the same person. Now merge two companies: one single email, saying the chief of company A now reports to the chief of company B. Nobody else is told anything, nobody updates their paperwork, and yet every one of A’s thousands of employees is now correctly in company B, because their walk just continues one hop further. To keep the walks short, everybody who does walk up the chain re-points themselves nearer the top on the way — the question pays for the tidying. Two places the picture breaks. Real firms have meaningful middle management, whereas here the internal shape means nothing at all: only the person at the top identifies the company, and the tidying gleefully destroys everything below. And real companies can demerge. This structure cannot — it only ever joins, never splits, and undoing a merge needs a completely different arrangement.
The test is whether the listener understands why merging is cheap — that almost nobody is told about a merge. A strong answer names the representative, the one-pointer merge, and the shortcut on the way up, then admits the thing the picture cannot do.