Disjoint Set Union

The problem

You have $n$ items and each starts alone in its own group. Two kinds of events happen:

• union(a, b): merge the group of $a$ with the group of $b$.
• find / same(a, b): are $a$ and $b$ in the same group? Sometimes also: how big is the group, how many groups are left?

A friendship network where new friendships keep appearing is the standard picture. Groups only merge, they never split.