AlgoScope

Union-Find Operations

find climbs to the root then flattens the path. Union hangs the smaller root under the larger.

Connectivity and topological order, algorithm, intermediate
find 0 reaches root 0 after 0 steps.0123456parsize01234561111111x
find 0 reaches root 0 after 0 steps.0123456parsize01234561111111x

Union-Find: Path compression at work

Decision, step 2 of 22

find(0): parent[0] = 0, so 0 is a root already. Its set is 0.

How union-find works

Cost

Best
O(1)
Average
O(alpha(n)) amortized
Worst
O(log n)
Space
O(n)

Taught by the same lesson

Union-Find covers these too, in the same run.