Union Find | Disjoint Set Union | Set Size
Prerequisite: DSU Optimizations
The introductory problem asked a yes-or-no question: do x and y live in the same cluster? This problem asks for a number: how many elements share the cluster that contains x?
The class supports two operations. merge(x, y) joins the clusters containing x and y. count(x) returns the size of the cluster containing x. As in the previous practice, labels can appear for the first time in any operation, so a new value starts as a singleton cluster of size 1.
Example
union 1 2 union 2 3 count 3 => 3 count 4 => 1
After union 1 2, the cluster {1, 2} has size 2. After union 2 3, that same cluster grows to {1, 2, 3}, so count 3 returns 3. The value 4 has not appeared before count 4, so it is created as its own singleton cluster and the answer is 1.