Деревья и графы. Система непересекающихся множеств. Поиск наименьшего общего предка.

• Теория графов

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

Структура данных "система непересекающихся множеств" (на английском "disjoint-set-union", или просто "DSU").

Эта структура данных предоставляет следующие возможности. Изначально имеется несколько элементов, каждый из которых находится в отдельном (своём собственном) множестве. За одну операцию можно объединить два каких-либо множества, а также можно запросить, в каком множестве сейчас находится указанный элемент. Также, в классическом варианте, вводится ещё одна операция — создание нового элемента, который помещается в отдельное множество.

Таким образом, базовый интерфейс данной структуры данных состоит всего из трёх операций:

• make_set(x) — добавляет новый элемент $x$, помещая его в новое множество, состоящее из одного него.
• union_sets(x,y) — объединяет два указанных множества (множество, в котором находится элемент $x$, и множество, в котором находится элемент $y$).
• find_set(x) - возвращает, в каком множестве находится указанный элемент $x$. На самом деле при этом возвращается один из элементов множества (называемый представителем или лидером (в англоязычной литературе "leader")). Этот представитель выбирается в каждом множестве самой структурой данных (и может меняться с течением времени, а именно, после вызовов union_sets()). Например, если вызов find_set() для каких-то двух элементов вернул одно и то же значение, то это означает, что эти элементы находятся в одном и том же множестве, а в противном случае — в разных множествах.

Описываемая ниже структура данных позволяет делать каждую из этих операций почти за $O(1)$ в среднем (более подробно об асимптотике см. ниже после описания алгоритма).