Disjoint Set Union
A parent array where following pointers leads to a root that names the set; union links two roots.
find(0): parent[0] = 0, so 0 is a root already. Its set is 0.
What you will see
A forest of parent pointers; find walks up and flattens the path; union hangs the smaller tree under the larger.
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.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.
Before this
Taught by the same lesson
Union-Find covers these too, in the same run.