What is union-find?
Union-Find (also called Disjoint Set Union) is a structure for tracking which items belong to the same group while groups keep merging. It runs on one rule: every member points toward a leader — the root of its group — and two members are in the same group exactly when they have the same root. Its two operations are its name: union merges two groups, find returns a member's root.
In this lesson you'll learn how a single parent array answers "same group?" instantly, how merges work by re-pointing one arrow, and the two small optimizations that make it near-constant time.
Where it matters: a social network keeps adding friendships one at a time, and you must answer instantly — are Ana and Ben in the same friend circle? how many circles are there? Connections and queries are interleaved, so you can't pre-process the graph once, and you don't care about the path between people — only whether they share a group. Think of friend circles where everyone points to a circle leader: to merge two circles, one leader starts pointing to the other; to check membership, follow the pointers up to each leader and compare.
Follow one story in words: Ana, Ben, Cai and Dev each start alone — four one-person circles, everyone leading themselves. Ana and Ben become friends: Ben's arrow points at Ana, who now leads the pair. Cai and Dev befriend too — a second circle, led by Cai. Now Ben befriends Dev. Their leaders shake hands: Cai's arrow points at Ana — one arrow changed, and both whole circles merged. "Are Dev and Ben in the same circle?" Follow Dev's arrows up: Dev → Cai → Ana. Ben's: Ben → Ana. Same leader — same circle. Watch the arrows below. (The coded union/find with path compression lives in the See it step.)
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).
The Parent Array in JavaScript
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
| step | operation | what happens | groups after |
|---|---|---|---|
| 1 | union(0, 1) | 1's leader becomes 0 | {0,1} {2} {3} {4} |
| 2 | union(2, 3) | 3's leader becomes 2 | {0,1} {2,3} {4} |
| 3 | 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. The code below returns the first cycle-closing edge.
Cycle Detection in JavaScript
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. The See it step animates the whole machine: arrows pointing up to leaders, a merge changing exactly one arrow, and path compression flattening the tree as a side effect of merely asking questions. 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). Next up in order: Intervals — merging and comparing ranges on a timeline.