← Lab

ðŸŒē Union-Find — parent[], path compression, union by rank

Track connected sets with a parent array. find walks to the root and flattens the path; union attaches the shorter tree under the taller. Near-O(1) per op.

ab
elements
8
disjoint sets
8
find/union
≈O(1)
a,b connected?
no
parent[i] — a root points to itself
0↑0
root
1↑1
root
2↑2
root
3↑3
root
4↑4
root
5↑5
root
6↑6
root
7↑7
root
what just happened (say it out loud)

Run an operation to see it step by step.

ė‚Žėƒ: Union-Find answers 'are these in the same set?' in near-constant time by keeping a forest in a flat array. Path compression + union-by-rank keep the trees almost flat, which is why the amortized cost is the inverse-Ackermann Îą(n) — effectively O(1).
â–ķ deep-dive videos — “union find disjoint set path compression union by rank”