Алгоритмы с нуля
Union-Find (система непересекающихся множеств): сжатие путей и объединение по рангу
В уроке про связные компоненты ты считал части графа перебирая вершины и запуская BFS/DFS из каждой непосещённой. Это работает прекрасно — но только если у тебя уже есть весь граф. А что если рёбра приходят по одному, и после каждого ты должен ответить «эти две вершины уже в одной части?» Пересчитывать все компоненты свежим BFS после каждого отдельного ребра расточительно. Union-Find — также называемый системой непересекающихся множеств (СНМ) — это структура данных созданная ровно для этого. Она поддерживает разбиение элементов на непересекающиеся множества и отвечает «то же множество?» и «слей эти два множества» за почти постоянное время. Это движок за динамической связностью, поиском циклов в неориентированном графе и минимальным остовным деревом Краскала.
После этого урока ты можешь реализовать СНМ как лес parent[], где каждый элемент начинает как свой собственный корень. Ты можешь написать find(x) (вернуть представителя/корень множества x) и union(a, b) (слить два множества), и объяснить connected(a, b) как find(a) === find(b). Ты понимаешь две оптимизации: объединение по рангу/размеру (прицепить более мелкое дерево под более глубокий корень) и сжатие путей (во время find перенаправить узлы ближе к корню). Ты знаешь что без них find это O(n) на вырожденной цепи, и что с обеими вместе каждая операция это амортизированно O(alpha(n)) — где alpha это обратная функция Аккермана, меньше 5 для любого входа который ты когда-либо увидишь — так что фактически почти константа, но не буквально O(1) на вызов. Ты можешь назвать применения: динамическая связность, поиск циклов в неориентированном графе, MST Краскала и инкрементальный подсчёт компонент. Ты можешь противопоставить СНМ (инкрементальная, рёбра приходят со временем) и компоненты BFS/DFS (статичные, пересчитывай всё заново).
Какую проблему решает Union-Find?
У тебя n элементов с номерами 0..n-1. Они сгруппированы в непересекающиеся множества (ни один элемент не в двух множествах). Две операции должны быть быстрыми:
- find(x) — вернуть канонического представителя («корень») множества которое содержит
x. Два элемента в одном множестве ровно тогда, когда у них один корень. - union(a, b) — слить множество содержащее
aс множеством содержащимbв одно множество.
Производный запрос, connected(a, b), это просто find(a) === find(b).
Лес parent[]
Каждое множество хранится как дерево. У каждого элемента есть parent. Корень дерева это элемент чей родитель он сам — этот корень и есть представитель множества. Изначально каждый элемент свой собственный родитель, так что у тебя n одиночных деревьев:
parent: index 0 1 2 3 4 5
value 0 1 2 3 4 5 (каждый указывает на себя = свой корень)
Лес: (0) (1) (2) (3) (4) (5) шесть отдельных множествfind(x) идёт вверх по указателям parent пока не достигнет корня. union(a, b) находит оба корня и указывает одним корнем на другой.
Наивный union и почему деревья могут вырождаться
Если ты всегда прицепляешь корень a под корень b вслепую, ты можешь построить длинную цепь:
union(1,0), union(2,1), union(3,2), union(4,3):
0 find(4) должен пройти: 4 -> 3 -> 2 -> 1 -> 0
^ Это 4 прыжка для n = 5 элементов.
1 Цепь из n узлов делает find O(n) — так же медленно как связный список.
^
2
^
3
^
4Весь смысл СНМ это держать эти деревья мелкими. Два независимых приёма это делают.
Оптимизация 1: объединение по рангу (или размеру)
Держи дополнительный массив rank[] (верхняя граница на высоту дерева). При слиянии двух корней, прицепи тот у кого меньший ранг под тот у кого больший ранг. Равные ранги: выбери любой как новый корень и увеличь его ранг на 1. Это само по себе держит деревья логарифмически мелкими — дерево ранга r имеет хотя бы 2^r элементов, так что высота никогда не превышает log2(n).
Объединение по размеру (отслеживай число элементов, прицепляй меньшее дерево под большее) даёт ту же границу и взаимозаменяемо. Здесь мы используем ранг.
Два множества, корни A (ранг 1) и B (ранг 0):
A (ранг 1) B (ранг 0) union(A, B): rank[A] > rank[B]
| -> прицепить B под A. Rank[A] остаётся 1.
x
A (ранг 1)
| \
x B мелкое, не цепьОптимизация 2: сжатие путей
Во время find(x), после того как ты находишь корень, перенаправь узлы по которым ты прошёл чтобы они указывали ближе к корню (в идеале прямо на него). В следующий раз эти узлы достигают корня за один прыжок. Простой, эффективный вариант это уполовинивание пути: сделай так чтобы каждый узел на пути указывал на своего деда пока ты поднимаешься.
До find(4): 0 После find(4) со сжатием:
^
1 0
^ / / | \
2 1 2 3 4 все теперь указывают близко к корню
^
3 Последующий find(4) почти O(1).
^
4Разобранный пример: построй, объедини, запроси
Начни с 6 одиночек. Примени union(0,1), union(2,3), union(1,3):
Начало: (0) (1) (2) (3) (4) (5) 6 множеств
union(0,1): корни 0 и 1, равный ранг.
parent[1] = 0, rank[0] = 1. -> {0,1} корень 0
union(2,3): корни 2 и 3, равный ранг.
parent[3] = 2, rank[2] = 1. -> {2,3} корень 2
union(1,3): find(1) = 0 (ранг 1), find(3) = 2 (ранг 1), равны.
parent[2] = 0, rank[0] = 2. -> {0,1,2,3} корень 0
Лес теперь:
0 (ранг 2)
/ | \
1 2 ... и 3 висит под 2
|
3
connected(1, 3) = (find(1) == find(3)) = (0 == 0) = true
connected(1, 4) = (0 == 4) = false
Число множеств: началось с 6, сделано 3 успешных union, 6 - 3 = 3 множества: {0,1,2,3}, {4}, {5}.Каждый успешный union уменьшает число множеств на единицу. Поддержка поля count даёт тебе число связных компонент бесплатно, обновляемое инкрементально по мере прихода рёбер.
СНМ против компонент BFS/DFS
Оба отвечают «в какой части это находится?», но они подходят под разные формы задач:
- Компоненты BFS/DFS (предыдущий урок): статичны. У тебя есть все рёбра, ты обходишь один раз, ты помечаешь каждую вершину. Добавить ребро заново означает пересчёт.
- Union-Find: инкрементальная / динамическая. Рёбра приходят со временем; после каждого
unionты можешь сразу запросить связность. Без повторного обхода. Вот почему СНМ это естественный выбор для MST Краскала (обрабатывай рёбра в порядке веса) и онлайн-связности.
СНМ со сжатием путей и объединением по рангу
1
class DSU {
2
constructor(n) {
3
// Each element starts as its own parent (a singleton set)
4
this.parent = Array.from({ length: n }, (_, i) => i);
5
this.rank = new Array(n).fill(0); // upper bound on tree height
6
this.count = n; // number of disjoint sets
7
}
8
9
find(x) {
10
// Walk to the root; path halving compresses as we climb
11
while (this.parent[x] !== x) {
12
this.parent[x] = this.parent[this.parent[x]]; // point x at its grandparent
13
x = this.parent[x];
14
}
15
return x;
16
}
17
18
union(a, b) {
19
let ra = this.find(a);
20
let rb = this.find(b);
21
if (ra === rb) return false; // already one set: nothing merges
22
// Union by rank: attach the smaller-rank tree under the larger
23
if (this.rank[ra] < this.rank[rb]) { const t = ra; ra = rb; rb = t; }
24
this.parent[rb] = ra;
25
if (this.rank[ra] === this.rank[rb]) this.rank[ra]++;
26
this.count--; // two sets became one
27
return true;
28
}
29
30
connected(a, b) {
31
return this.find(a) === this.find(b);
32
}
33
}
- L4 parent[i] = i: каждый элемент изначально свой собственный корень.
- L5 rank приближает высоту дерева; важны только ранги корней.
- L6 Отслеживай живое число множеств чтобы подсчёт компонент был O(1).
- L11 Цикл пока x не корень (parent указывает на себя).
- L12 Уполовинивание пути: перенаправь x на его деда, распрямляя дерево.
- L19 Сначала найди оба корня; если равны, множества уже слиты.
- L22 Объединение по рангу: убедись что ra это более глубокий корень (с большим рангом).
- L23 Повесь более мелкий корень rb под более глубокий корень ra.
- L24 Равные ранги: слитое дерево стало на уровень выше — увеличь ранг.
- L25 Успешный union уменьшает число непересекающихся множеств на единицу.
Ключевой момент: обе оптимизации нужны для границы alpha(n)
Объединение по рангу само по себе ограничивает высоту O(log n). Сжатие путей само по себе тоже сильно помогает. Использованные вместе, амортизированная стоимость на операцию схлопывается до O(alpha(n)) — обратной функции Аккермана, которая ниже 5 для любого n что помещается во вселенную. Убери обе и find это O(n) на вырожденной цепи.
Запуск СНМ: построй множества, объедини, запроси, посчитай
1
dsu = new DSU(6); // parent[i] = i, rank = 0, count = 6
2
dsu.union(0, 1);
3
dsu.union(2, 3);
4
dsu.union(1, 3);
5
dsu.connected(1, 3);
Без оптимизаций: find это O(n) в худшем случае
Простой лес parent[] с наивным union может построить цепь из n элементов (каждый новый корень прицеплен под предыдущий). Тогда find на самом глубоком элементе проходит n - 1 указателей parent: O(n) на операцию. Последовательность из m операций стоит до O(m * n) — не лучше связного списка.
Наивная цепь (n = 5): 0 <- 1 <- 2 <- 3 <- 4
find(4) проходит 4 -> 3 -> 2 -> 1 -> 0 = 4 прыжка = n - 1 = O(n)Только объединение по рангу: O(log n)
Прицепление дерева с меньшим рангом под большее гарантирует что дерево ранга r держит хотя бы 2^r элементов, так что высота никогда не превышает log2(n). Каждый find тогда O(log n).
Обе вместе: амортизированно O(alpha(n)) — почти константа
Совмести объединение по рангу со сжатием путей и амортизированная стоимость на операцию падает до O(alpha(n)), где alpha это обратная функция Аккермана. Функция Аккермана растёт так взрывообразно что её обратная растёт почти незаметно: alpha(n) это самое большее 4 (обычно указывается как < 5) для каждого n вплоть до астрономически больших значений — далеко за пределами числа атомов во вселенной. Так что на практике каждый find/union ведёт себя как операция почти постоянного времени.
Будь точен с утверждением. Это амортизированно O(alpha(n)) усреднённо по последовательности операций, не гарантированное O(1) для каждого отдельного вызова, и это доказуемо не истинное постоянное время (Тарьян доказал нижнюю границу alpha(n) для структур такого стиля). Это также лучше чем O(log n) — не указывай O(log n) как оптимизированную границу.
n alpha(n)
2 1
4 2
16 3
65536 4
2^65536 4 (всё ещё 4 — астрономически большой вход)Память: O(n)
Два массива длины n (parent и rank), плюс опциональный count: O(n) всего. find и union используют O(1) дополнительной памяти (итеративный find с уполовиниванием пути не требует стека рекурсии).
Что возвращает find(x) в структуре Union-Find?
Какова цель объединения по рангу (или размеру)?
Что делает сжатие путей во время find(x)?
С ОБЕИМИ объединением по рангу и сжатием путей, какое амортизированное время на операцию?
Почему Union-Find подходит лучше чем перезапуск BFS/DFS для динамической связности (рёбра приходят со временем)?
Ты начинаешь с 8 непересекающихся одиночек и выполняешь 3 успешных union (каждый сливает два разных множества). Сколько непересекающихся множеств остаётся?
Почему это работает
Почему find(a) === find(b) это тест на связность. Каждый элемент в множестве достигает того же корня идя по указателям parent, и корни уникальны на множество. Так что два элемента связаны тогда и только тогда когда их find приходят к одному корню. Так же работает и поиск циклов в неориентированном графе: обрабатывай каждое ребро (u, v); если find(u) === find(v) ребро замыкает цикл (оба конца уже в одном множестве); иначе объедини их. MST Краскала использует ровно ту же проверку чтобы отклонить рёбра которые образовали бы цикл.
Частая ошибка
Сравнение голых родителей вместо корней. Частая ошибка это проверять parent[a] === parent[b] или объединять записывая parent[a] = b (элемент, не его корень). Оба неверны: связность это про корни, не непосредственных родителей. Всегда сначала вызывай find на обоих элементах, потом связывай два корня. Связывание не-корней портит лес и ломает будущие запросы.
Граничные случаи
Union на элементах уже в одном множестве. Если find(a) === find(b), элементы уже слиты. Корректный union должен это обнаружить и ничего не делать (здесь он возвращает false и оставляет count без изменений). Забыть эту проверку — значит неправильно уменьшить число множеств и, в поиске циклов, ты пропустил бы что ребро на самом деле замкнуло цикл. В этом уроке ранний if (ra === rb) return false; это обрабатывает.
Ещё практика
Объединение по размеру как замена один-в-один. Вместо rank[], держи size[] (число элементов под каждым корнем, инициализированное в 1). При union, прицепи корень с меньшим размером под больший и сложи размеры. Граница сложности идентична объединению по рангу, и размер часто удобнее потому что ты можешь запросить «насколько велика компонента x?» за O(1) читая size[find(x)]. Выбирай что нужно задаче; никогда не пропускай обе, иначе деревья могут выродиться до O(n).
Объясни что такое Union-Find (СНМ), как find и union работают на лесу parent[], что делают объединение по рангу и сжатие путей, корректную оптимизированную сложность, и когда использовать СНМ вместо BFS/DFS.
Union-Find (система непересекающихся множеств) поддерживает разбиение элементов как лес parent[]: каждое множество это дерево, а корень это его представитель.
Операции: find(x) идёт по указателям parent до корня; union(a, b) связывает один корень под другим; connected(a, b) это find(a) === find(b). Отслеживай count чтобы читать число связных компонент инкрементально.
Две оптимизации: объединение по рангу/размеру прицепляет более мелкое дерево под более глубокий корень; сжатие путей распрямляет путь во время find. Вместе они дают амортизированно O(alpha(n)) — обратную функцию Аккермана, ниже 5 для любого практического n, так что почти константа (но не истинное O(1), и лучше чем O(log n)). Без них, find это O(n) на вырожденной цепи. Память: O(n).
Когда тянуться за ней: динамическая связность, поиск циклов в неориентированном графе, MST Краскала и инкрементальный подсчёт компонент — везде где рёбра приходят со временем и где иначе ты пересчитывал бы компоненты BFS/DFS с нуля.