Union-Find (система непересекающихся множеств)

Коротко: Union-Find управляет группами элементов и очень быстро отвечает, принадлежат ли два элемента одной группе и как объединить две группы.

Подробнее: Каждая группа хранится как дерево, корень которого представляет группу. find(x) идёт по родителям до корня, union(a, b) подвешивает один корень под другой.