Step 6 of 6

Challenge: union-find

Union-find (disjoint set union) tracks which items are in the same group while groups keep merging: network connectivity, clustering, Kruskal's minimum spanning tree, detecting cycles as edges arrive.

Each set is a tree; find(x) walks to the root, which identifies the set. Two tricks make it nearly O(1) per operation:

• path compression: while finding, point nodes directly at the root
• union by size: attach the smaller tree under the larger one

Your turn: write class UnionFind:

• explicit UnionFind(int n): n separate sets
• int find(int x) with path compression
• bool unite(int a, int b): merge; returns false if already in the same set
• int groups() const: number of separate sets
• int size_of(int x): size of x's set

Previous: Dijkstra's shortest paths