Union-Find Operations
find climbs to the root then flattens the path; union hangs the smaller root under the larger.
Decision · step 2 of 22Union-Find: Path compression at work
find(0): parent[0] = 0, so 0 is a root already. Its set is 0.
What you will see
find climbs to the root then flattens the path; union hangs one root under the other.
Cost
| Best | O(1) |
|---|---|
| Average | O(alpha(n)) amortized |
| Worst | O(log n) |
| Space | O(n) |
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, predict what happens next.
Screen readers: Vertices announce name, discovery numbers where relevant and component; each step announces the structural conclusion (bridge found, component closed).
Reduced motion: Component colouring and ordering changes crossfade in place.