Union-find
Each group is a little tree, and every node points toward its group's root. To link two nodes, find both roots and hang one under the other. Two tricks keep the trees flat: hang the smaller group under the bigger, and shortcut nodes past their parent whenever you walk up.
parent[x]: follow it up to the root of x's group
A
AB
BC
CD
DE
EF
FG
GH
HEvery node starts in a group of its own, as its own root. Add the 7 links one at a time.
1function find(parent, x) {2 while (parent[x] !== x) {3 parent[x] = parent[parent[x]];4 x = parent[x];5 }6 return x;7}89function union(parent, size, a, b) {10 let ra = find(parent, a), rb = find(parent, b);11 if (ra === rb) return false;12 if (size[ra] < size[rb]) [ra, rb] = [rb, ra];13 parent[rb] = ra;14 size[ra] += size[rb];15 return true;16}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | 1 | the node points straight at its root |
| average | α(n) | with both tricks: under 5 for any real n |
| worst | log n | for a single find, with union by size |
| space | n | a parent and a size per node |
Where it breaks
- Without the tricks it can degrade. Always hanging the first root under the second can build one long chain, and every find walks all of it. Union by size alone caps the height at log n.
- It only joins, never splits. Union-find has no cheap way to remove a link. If links come and go, recompute the groups or use a heavier structure.
- Spotting a redundant link. Pick Repeat links: when both ends already share a root, the link would close a loop. Kruskal's algorithm uses exactly this to skip edges.