AlgoScope

Disjoint Set Union

A parent array where following pointers leads to a root that names the set. Union links two roots.

Data structures, data structure, intermediateAlso called union-find, DSU
find 0 reaches root 0 after 0 steps.01234567parsize0123456711111111x
find 0 reaches root 0 after 0 steps.01234567parsize0123456711111111x

Union-Find: Merging sets by size

Decision, step 2 of 24

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

Cost

Find
O(alpha(n)) amortized
Union
O(alpha(n)) amortized
Space
O(n)

With path compression and union by rank. Alpha is the inverse Ackermann function.

Leads to

Topics that need this one first.

Taught by the same lesson

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