Информатика / Алгоритмы и анализ данных
Система непересекающихся множеств: объединение и поиск корня
Система непересекающихся множеств (DSU, или union–find) хранит разбиение элементов на компоненты. Операция find находит представителя компоненты, а union объединяет две компоненты; с эвристиками сжатия пути и объединения по размеру амортизированная стоимость операции равна O(α(n)).
Формула
В примере 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)). Без эвристик та же последовательность может деградировать до квадратичной.
Как пользоваться формулой
- Создайте массив parent и присвойте parent[x]=x для каждого элемента x, а начальный size[x] установите равным единице.
- Для find(x) поднимайтесь по parent до вершины, у которой parent равен ей самой; эта вершина представляет всё множество.
- При возврате из find переподчините посещённые вершины найденному корню, чтобы следующие запросы проходили по короткому пути.
- Для union(a,b) найдите корни r=find(a) и s=find(b); если они совпали, состояние и размеры компонент оставьте без изменений.
- Сравните size[r] и size[s], выберите большим корнем тот, у кого размер не меньше, и подвесьте меньший корень к нему.
- После каждого объединения при необходимости проверяйте связность запросом 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
Связанные формулы
Информатика
Алгоритм Краскала: вес минимального остовного дерева
Алгоритм Краскала строит минимальное остовное дерево неориентированного графа: перебирает рёбра по возрастанию веса и принимает только те, которые соединяют разные текущие компоненты.
Информатика
Мосты графа: критерий через времена входа и low
Мост — ребро неориентированного графа, удаление которого увеличивает число компонент связности. DFS обнаруживает его, если поддерево ребёнка не имеет обходного ребра к родителю или его предкам.
Информатика
Алгоритм Дейкстры: релаксация и кратчайшие расстояния
Алгоритм Дейкстры находит кратчайшие пути от одной вершины при неотрицательных весах рёбер. На каждом шаге окончательно выбирается ещё не выбранная вершина с минимальной текущей меткой.
Информатика
Сильные компоненты: два обхода алгоритма Косарайю
Сильная компонента ориентированного графа объединяет вершины, достижимые друг из друга в обоих направлениях. Алгоритм Косарайю находит такие группы двумя обходами в глубину с разворотом всех дуг.