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

Введение

Система непересекающихся множеств (DSU) — это структура данных для поддержания коллекции непересекающихся множеств.

Изначально каждый элемент принадлежит своему собственному множеству. Затем DSU поддерживает операции, которые позволяют нам объединять множества и определять, к какому множеству принадлежит данный элемент.

В классической версии DSU поддерживает три операции:

• make_set(x) — создать новое множество, содержащее только элемент x;
• find_set(x) — найти представителя (лидера) множества, содержащего x;
• union_sets(x, y) — объединить множества, содержащие x и y.

Реализация

Каждое множество представляется как укоренённое дерево.

• вершины дерева — это элементы множества;
• корень дерева называется лидером (или представителем) множества.

Таким образом, DSU хранит лес деревьев, где каждое дерево соответствует одному множеству.

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

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

Чтобы реализовать эту идею, мы используем массив parent, где parent[x] хранит родителя вершины x.

Если x — корень своего дерева, то parent[x] = x.

Операции

• make_set(x)
  Создать новое множество, содержащее только x.

• find_set(x)
  Найти корень дерева, содержащего x.

• union_sets(x, y)
  Сначала найти лидеров x и y. Если они различны, присоединить одно дерево к другому.

В худшем случае и find_set, и union_sets могут занимать $O(n)$ времени.

Более быстрое решение: объединение по размеру