Disjoint Set Union
A parent array where following pointers leads to a root that names the set. Union links two roots.
Union-Find: Merging sets by size
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.
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Union-Find covers these too, in the same run.