Информатика / Алгоритмы и анализ данных

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

Система непересекающихся множеств (DSU, или union–find) хранит разбиение элементов на компоненты. Операция find находит представителя компоненты, а union объединяет две компоненты; с эвристиками сжатия пути и объединения по размеру амортизированная стоимость операции равна O(α(n)).

Опубликовано: Обновлено:

Формула

$$r=\operatorname{find}(a),\;s=\operatorname{find}(b),\;size[r]\ge size[s]\Rightarrow parent[s]\leftarrow r,\;size[r]\leftarrow size[r]+size[s],\qquad T=O(n+m\alpha(n))$$
Схема Сжатие пути для вершины 4
До find(4)После find(4)12341234

В примере 4 указывает на 3, а 3 — на 1. После find(4) ссылка 4 ведёт прямо к 1; вершина 2 уже указывает на 1.

Обозначения

$parent[x]$
родитель вершины x в лесу DSU, индекс
$size[x]$
размер дерева, если x — корень, элементы
$a,b$
элементы, которые нужно объединить, индексы
$r,s$
корни a и b перед union, индексы
$n$
число элементов инициализации, шт.
$m$
число операций find и union после инициализации, операции
$α(n)$
обратная функция Аккермана, безразмерная

Условия применения

Изначально каждый из n элементов образует отдельное множество; удаление связей не предусмотрено. Каждый корень удовлетворяет parent[root]=root. Для union сначала находят r=find(a) и s=find(b); если r=s, состояние не меняется. Иначе выбирают size[r]≥size[s], подвешивают s к r и увеличивают size[r]. При find посещённые вершины направляются непосредственно к найденному корню.

Ограничения

DSU не хранит кратчайшие пути, расстояния или порядок обхода внутри компоненты. Если нужны удаления рёбер, откат операций или динамическая связность во времени, требуются расширения: DSU с откатами, офлайн-обработка или другая структура данных.

Подробное объяснение

Внутреннее представление DSU — лес ориентированных деревьев. Сначала parent[x]=x для всех x, поэтому find(x) возвращает сам x. Когда появляется связь между a и b, сначала находятся корни r и s. Если они совпадают, новое ребро не меняет разбиение; если различаются, корень меньшего дерева становится потомком корня большего. Эвристика размера не даёт деревьям расти цепочкой: меньшее дерево прикрепляется к большему.

Сжатие пути ускоряет последующие запросы. Во время рекурсивного find вершина получает ссылку сразу на корень, поэтому длинная цепочка превращается в почти плоское дерево. Эти две эвристики вместе дают амортизированную оценку; функция α растёт настолько медленно, что для практических размеров n её значение не превышает нескольких единиц.

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

Важно различать число операций и стоимость одной операции. Для n элементов и m последующих find/union полная последовательность занимает O(n+mα(n)); при m≥n это обычно записывают как O(mα(n)). Без эвристик та же последовательность может деградировать до квадратичной.

Как пользоваться формулой

  1. Создайте массив parent и присвойте parent[x]=x для каждого элемента x, а начальный size[x] установите равным единице.
  2. Для find(x) поднимайтесь по parent до вершины, у которой parent равен ей самой; эта вершина представляет всё множество.
  3. При возврате из find переподчините посещённые вершины найденному корню, чтобы следующие запросы проходили по короткому пути.
  4. Для union(a,b) найдите корни r=find(a) и s=find(b); если они совпали, состояние и размеры компонент оставьте без изменений.
  5. Сравните size[r] и size[s], выберите большим корнем тот, у кого размер не меньше, и подвесьте меньший корень к нему.
  6. После каждого объединения при необходимости проверяйте связность запросом find(u)=find(v), сравнивая именно корни, а не непосредственных родителей.

Историческая справка

Идея поддержания разбиения на классы эквивалентности возникла из задач обработки лесов и алгоритмов на графах. В статье Роберта Тарьяна «Efficiency of a Good But Not Linear Set Union Algorithm», опубликованной в Journal of the ACM в 1975 году, строго исследовано сочетание сжатия пути и объединения по рангу и получена оценка через обратную функцию Аккермана. Практическая форма union–find стала стандартной частью алгоритма Краскала, опубликованного Джозефом Краскалом в 1956 году для построения минимального остовного дерева.

Современная запись parent и size — инженерная реализация этой идеи. В учебных алгоритмах рекурсивный find часто показывают вместе с присваиванием parent[x]=find(parent[x]); в итеративных реализациях те же изменения выполняют двумя проходами. Для n элементов и m последующих операций полная оценка включает инициализацию O(n): O(n+mα(n)); если m≥n, её часто сокращают до O(mα(n)). Теоретическая оценка описывает последовательность операций, а не худший случай каждой отдельной строки.

Историческая линия формулы

У union–find нет единственного автора. Структура выросла из алгоритмов эквивалентности и лесов; современная оценка сочетания эвристик связана с работами Роберта Тарьяна. Алгоритм Краскала — отдельное применение DSU к минимальному остовному дереву.

Пример

Пусть элементы 1, 2, 3, 4, 5 изначально независимы. Выполним union(1,2), union(3,4), union(2,3). После первого шага parent[2]=1 и size[1]=2; после второго parent[4]=3 и size[3]=2. В третьем шаге r=find(2)=1 и s=find(3)=3, размеры равны, поэтому parent[3]=1 и size[1]=4. Теперь find(4) проходит через 3, сжимает путь и возвращает 1. Элементы 4 и 5 связаны? Нет: find(4)=1, find(5)=5, поэтому 5 ещё в отдельной компоненте. Повторный find(4) уже обращается к корню напрямую, что и показывает эффект сжатия пути. Число операций постоянно, а индексы и размеры не имеют физических единиц.

Частая ошибка

Частая ошибка — сравнивать parent[a] и parent[b] вместо корней: непосредственные родители могут различаться даже внутри одной компоненты. Нельзя выполнять union без проверки ra=rb, иначе размер компоненты будет посчитан дважды. Сжатие пути должно менять parent посещённых вершин, а не только возвращать корень. Наконец, DSU не подходит для удаления связи: после объединения разделить компоненту одной операцией невозможно.

Практика

Задачи с решением

Компоненты после слияний

Условие. Есть 6 элементов и операции union(1,2), union(2,3), union(5,6). Сколько компонент останется?

Решение. Первые две операции дают {1,2,3}; третья — {5,6}. Отдельно остаются 4, поэтому компоненты: {1,2,3}, {4}, {5,6}.

Ответ. 3 компоненты.

Проверка цикла

Условие. В DSU корни вершин 7 и 9 совпали. Можно ли добавить ребро (7,9) в лес без цикла?

Решение. Нет. Совпадение корней означает, что путь между вершинами уже существует; добавление ребра замкнёт цикл.

Ответ. Ребро отклоняют.

Дополнительные источники

  • https://doi.org/10.1145/321879.321884
  • https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/UnionFind.pdf

Связанные формулы

Информатика

Алгоритм Краскала: вес минимального остовного дерева

$T\in\underset{\text{остовные деревья }S}{\operatorname{arg\,min}}\sum_{e\in S}w(e),\qquad |T|=V-1$

Алгоритм Краскала строит минимальное остовное дерево неориентированного графа: перебирает рёбра по возрастанию веса и принимает только те, которые соединяют разные текущие компоненты.

Информатика

Мосты графа: критерий через времена входа и low

$(v,u)\text{ — мост}\iff low(u)>t_{in}(v),\quad u\text{ — ребёнок }v\text{ в DFS}$

Мост — ребро неориентированного графа, удаление которого увеличивает число компонент связности. DFS обнаруживает его, если поддерево ребёнка не имеет обходного ребра к родителю или его предкам.

Информатика

Алгоритм Дейкстры: релаксация и кратчайшие расстояния

$d(v)\leftarrow\min\bigl(d(v),d(u)+w(u,v)\bigr),\qquad w(u,v)\geq0$

Алгоритм Дейкстры находит кратчайшие пути от одной вершины при неотрицательных весах рёбер. На каждом шаге окончательно выбирается ещё не выбранная вершина с минимальной текущей меткой.

Информатика

Сильные компоненты: два обхода алгоритма Косарайю

$u\sim v\iff(u\leadsto v)\land(v\leadsto u),\qquad T=O(|V|+|E|)$

Сильная компонента ориентированного графа объединяет вершины, достижимые друг из друга в обоих направлениях. Алгоритм Косарайю находит такие группы двумя обходами в глубину с разворотом всех дуг.