What union-find is
A social network keeps adding friendships one at a time, and you must answer two questions instantly: are Ana and Ben in the same friend circle? and how many separate circles are there? The twist: connections and queries are interleaved, so you can't pre-process the graph once. Re-running BFS/DFS per query is
O(n) each and re-explores the graph endlessly — and you don't care about the path, only whether two people share a group.Union-Find (a.k.a. Disjoint Set Union) tracks groups with one rule: every member points toward a leader — the root of its group. Two members are in the same circle exactly when they have the same root: It's friend circles where everyone points to a circle leader: to merge two circles you make one leader point to the other; to check membership you follow pointers up to each leader and compare.
In the animation, watch the arrows: every element points up toward its leader, and a merge changes exactly one arrow — one root bows to the other. Nobody else in either group moves.
This section has a step-by-step animation in the interactive lesson.
Quick check
Two elements are in the same group exactly when…
Answer it in the interactive lesson to keep your progress.
The core operations
Everything runs on one
parent array, where parent[i] is i's parent (itself if it's a leader):- make-set — start every element as its own parent:
[0, 1, 2, …]. - find(x) — walk up
parentuntil you reach a root (whereparent[x] === x); that root names the group. - union(a, b) —
findboth roots, then link one under the other.
Two optimizations make these nearly constant time: path compression (point nodes straight at the root during find) and union by rank/size (attach the smaller tree under the larger). Here's the starting state:
const n = 6;
const parent = Array.from({ length: n }, (_, i) => i);
console.log('start:', parent); // [0,1,2,3,4,5]
console.log('is 3 a root?', parent[3] === 3); // true — every node is a root at firstQuick check
parent = [0, 0, 1, 3, 3]. Predict find(2).
Answer it in the interactive lesson to keep your progress.
Your first union-find problem: detect a cycle
As friendships are added between people
0..4, detect the first edge that closes a loop — one that connects two people who are already in the same group. Union-Find answers "same group?" instantly by giving every group a single leader (root).The steps
- Start every element as its own leader (
parent[i] = i). - For each edge
(a, b): find the root ofaand the root ofb(walk up parents until a node is its own parent). - If the two roots are the same,
aandbare already connected → this edge closes a cycle. - Otherwise union them: point one root at the other, merging the groups.
Trace it on 0 1 2 3 4:
- union(0, 1) →
1's leader becomes0. Groups:{0,1},{2},{3},{4}. - union(2, 3) →
{0,1},{2,3},{4}. - find(1) vs find(0) → both lead to
0→ same group.
So if an edge's two ends already share a root, adding it would close a cycle. In JavaScript, one way to write those steps (it returns the first cycle-closing edge):
function firstCycleEdge(n, edges) {
const parent = Array.from({ length: n }, (_, i) => i);
const find = (x) => { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; };
for (const [a, b] of edges) {
const ra = find(a), rb = find(b);
if (ra === rb) return [a, b]; // both ends already connected → cycle
parent[ra] = rb;
}
return null; // no cycle
}
console.log(firstCycleEdge(3, [[0,1],[1,2],[2,0]])); // [2, 0]
console.log(firstCycleEdge(3, [[0,1],[1,2]])); // nullQuick check
An edge (a, b) closes a cycle when…
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
- Skipping path compression. Without it, chains grow long and
finddegrades towardO(n). Flatten the path on the way up — it is a couple of lines for a massive speedup. - Unioning nodes, not roots.
unionmust link the roots of the two groups, not the raw elements — otherwise you build wrong or tangled trees. Alwaysfindfirst. - Union by rank forgotten. Attaching the bigger tree under the smaller one makes trees taller than needed; attach small-under-large.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, with both optimizations
find and union run in O(α(n)) amortized — where α is the inverse-Ackermann function, effectively a small constant (≤ 4 for any real input). So a whole stream of merges and queries is near-linear overall, with O(n) space for the parent array.Key takeaways:
- Every element points toward a root; same root ⇔ same group.
- union links roots (always
findfirst); find walks up to the root. - Path compression + union by rank → near-constant
O(α(n))per operation.
This is the specialist tool for dynamic connectivity under a stream of merges. These classics each get their own lesson later (no need to know them yet): number of provinces / connected components (union every edge, count roots), redundant connection (the edge that first joins two already-connected nodes), and Kruskal's minimum spanning tree (add edges cheapest-first, skipping cycles).
In the closing animation, watch what path compression does on each find: every node visited on the way up is re-pointed straight at the root, so the tree flattens as a side effect of merely asking questions. Next up in order: Intervals — merging and comparing ranges on a timeline.
This section has a step-by-step animation in the interactive lesson.