Система непересекающихся множеств

Система непересекающихся множеств

Введение

DSU (Disjoint Set Union) предоставляет следующие возможности: нам дано несколько элементов, каждый из которых изначально является отдельным множеством. DSU поддерживает операцию объединения любых двух множеств и позволяет определить, в каком множестве находится конкретный элемент. В классическом варианте вводится и третья операция — создание множества из нового элемента.

Таким образом, интерфейс DSU состоит из трёх функций:

• make_set(x) — создаёт новое множество из одного элемента $x$.
• find_set(x) — находит множество, в котором находится элемент $x$ (обычно возвращает лидера множества).
• union_sets(x, y) — объединяет множества, содержащие элементы $x$ и $y$.

Реализация

Каждое множество будем представлять в виде корневого дерева. Вершины — это элементы множества. Корень дерева называют лидером множества. Тогда получается лес деревьев, где каждое дерево соответствует одному множеству.

Две вершины находятся в одном множестве тогда и только тогда, когда лидеры их деревьев совпадают.

Наивное решение

Создадим массив parent, где parent[x] — предок вершины (и для корня).