Community Article

Union-Find with Path Compression, Step by Step

Four implementations of union-find, in order: naive, union by rank, path compression, both combined. Watch the per-operation cost drop from O(n) to inverse-Ackermann at each stage.