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

TL;DR

Система непересекающихся множеств (disjoint-set data structure; DSU, union–find) хранит разбиение набора элементов на непересекающиеся множества и поддерживает три операции: Make-Set (создать множество из одного элемента), Find-Set (найти представителя множества) и Union (слить два множества). Её ключевое свойство — элементы можно только объединять, разбить множество обратно обычный DSU не умеет. Наивная реализация работает за [math]\displaystyle{ O(n) }[/math] на операцию, но две простые оптимизации — объединение по рангу и сжатие путей — вместе дают амортизированное [math]\displaystyle{ O(\alpha(n)) }[/math], где [math]\displaystyle{ \alpha }[/math] — обратная функция Аккермана, практически константа ([math]\displaystyle{ \alpha(n) \le 4 }[/math] для всех реальных [math]\displaystyle{ n }[/math]). Именно поэтому DSU — сердце алгоритма Краскала, применяется для компонент связности, обнаружения циклов, классов эквивалентности и офлайн-задач динамической связности.

Инфобокс

Свойство	Значение
Класс	Структура данных для разбиения (partition) множества
Операции	`Make-Set`, `Find-Set`, `Union`
Изобретение	Галлер и Фишер, 1964; анализ — Тарджан, 1975 [2][3]
Сложность (наивно)	[math]\displaystyle{ O(n) }[/math] на `Find`
Сложность (union by rank)	[math]\displaystyle{ O(\log n) }[/math]
Сложность (сжатие путей)	[math]\displaystyle{ O(\log n) }[/math] амортизированно
Сложность (обе вместе)	[math]\displaystyle{ O(\alpha(n)) }[/math] амортизированно — практически [math]\displaystyle{ O(1) }[/math]
Память	[math]\displaystyle{ O(n) }[/math] — массив `parent[]` (+ `size`/`rank`)
Обратная операция	`Split` (разбиение) — обычный DSU не поддерживает
Варианты	взвешенный DSU (потенциалы), DSU с откатом (rollback), персистентный DSU
Где встречается	Краскал, компоненты связности, детекция циклов, классы эквивалентности, офлайн-связность, LCA Тарджана

Определения

Разбиение (partition) множества [math]\displaystyle{ U }[/math] — семейство попарно непересекающихся непустых подмножеств, объединение которых равно [math]\displaystyle{ U }[/math]. Одно такое подмножество называется классом; говорят, что элементы одного класса эквивалентны.

Представитель (representative) множества — выделенный элемент класса (например, корень дерева), однозначно идентифицирующий множество.

Система непересекающихся множеств (DSU / union–find) — структура, поддерживающая разбиение и три операции:

Операция	Смысл	Постусловие
`Make-Set(x)`	создать новое множество [math]\displaystyle{ \{x\} }[/math]	[math]\displaystyle{ x }[/math] — отдельный класс, представитель [math]\displaystyle{ x }[/math]
`Find-Set(x)`	представитель класса [math]\displaystyle{ x }[/math]	`Find-Set(x) = Find-Set(y)` ⟺ [math]\displaystyle{ x, y }[/math] в одном классе
`Union(x, y)`	слить классы [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math]	два класса заменены их объединением

Формально DSU реализует отношение эквивалентности: [math]\displaystyle{ x \sim y }[/math] тогда и только тогда, когда Find-Set(x) = Find-Set(y).

Лес (forest representation). Каждое множество — дерево, корень которого является представителем. Узел хранит parent[] (у корня — сам себя), а также rank[] или size[] для оптимизации объединения.

Обратная функция Аккермана [math]\displaystyle{ \alpha(n) }[/math] — крайне медленно растущая функция: [math]\displaystyle{ \alpha(n) \le 4 }[/math] (при стандартном определении) для всех [math]\displaystyle{ n }[/math], которые можно записать в физической вселенной. Для [math]\displaystyle{ n = 10^9 }[/math] [math]\displaystyle{ \alpha(n) = 4 }[/math], тогда как [math]\displaystyle{ \log_2 n \approx 30 }[/math].

Обозначения. [math]\displaystyle{ n }[/math] — число элементов, [math]\displaystyle{ m }[/math] — суммарное число операций; если не оговорено, амортизированные оценки относятся к последовательности операций. parent[x], rank[x], size[x] — массивы по индексам элементов.

См. рис. 1: интерфейс и пример разбиения.

Рис. 1. DSU хранит разбиение на непересекающиеся множества и поддерживает Make-Set, Find-Set, Union. Разбиение обратно не поддерживается.

Мотивация и интуиция

Задачи «в одной ли группе эти два объекта?» и «объединить группы» возникают постоянно: при построении MST (Краскал), при поиске компонент связности, при обработке отношений эквивалентности, при проверке непротиворечивости ограничений. Наивное решение — перенумеровывать метки группы у всех элементов при каждом слиянии — стоит [math]\displaystyle{ O(n) }[/math] на операцию.

Идея DSU — представить каждое множество деревом, а не плоским списком. Тогда слияние — это подвешивание корня одного дерева под корень другого за [math]\displaystyle{ O(1) }[/math], а принадлежность проверяется поиском корня. Поиск может быть медленным при вырожденных деревьях, но две оптимизации это лечат:

объединение по рангу не даёт дереву вытянуться в цепь (высота [math]\displaystyle{ O(\log n) }[/math]);
сжатие путей во время поиска «сплющивает» длинные ветви.

Вместе они делают почти каждую операцию константной. Это редкий случай, когда очень простая структура имеет почти идеальную амортизированную сложность — и один из первых примеров амортизационного анализа, где оптимальность доказана с точностью до [math]\displaystyle{ \alpha(n) }[/math].

Устройство

Возможны два представления множества:

Связный список: множество — список, представитель — голова. Слияние за [math]\displaystyle{ O(1) }[/math] со ссылкой на хвост, но при перевешивании приходится обновлять представителя у всех элементов ([math]\displaystyle{ O(\text{size}) }[/math]).
Лес (деревья): множество — дерево, представитель — корень. Слияние — подвесить корень одного дерева под корень другого за [math]\displaystyle{ O(1) }[/math]. Это представление и используют на практике.

В лесном представлении нужны ровно два массива: parent[1..n] и один из rank[1..n] / size[1..n]. Индексы — элементы; значение parent[x] — «начальник» узла, у корня parent[x] = x. Высота дерева определяет стоимость Find; её контролируют Union по рангу и сжатие путей.

См. рис. 2: сравнение списка и леса.

Рис. 2. Связный список даёт [math]\displaystyle{ O(1) }[/math] слияние, но дорогое обновление представителя; лес даёт [math]\displaystyle{ O(1) }[/math] слияние ценой пути к корню, который и укорачивают оптимизациями.

Операции и алгоритмы

Операция: создать множество (Make-Set)

Идея. Сделать элемент отдельным деревом из одной вершины.

Алгоритм Make-Set(x)
1  parent[x] ← x
2  rank[x] ← 0          # или size[x] ← 1

Сложность: O(1).
Корректность: {x} — корректный одноэлементный класс, x — его представитель.

Операция: найти представителя (Find-Set)

Идея. Идти от узла вверх по parent до корня. Затем сжать путь: все пройденные узлы переподвесить прямо к корню, чтобы будущие поиски были короче.

Пошаговое описание.

Найти корень: parent[root] = root.
Пока не дошли — идти вверх.
Вторым проходом переподвесить все узлы пути к корню.

Инвариант. parent задаёт лес; корень каждого дерева — представитель своего класса. Сжатие путей не меняет разбиение, только структуру деревьев.

Псевдокод (полное сжатие, итеративно).

Алгоритм Find-Set(x)
Вход:  x — элемент
Выход: корень (представитель) класса x
1  root ← x
2  while parent[root] ≠ root
3      root ← parent[root]
4  while parent[x] ≠ root            # сжатие пути
5      next ← parent[x]
6      parent[x] ← root
7      x ← next
8  return root

Сложность: O(высота дерева); амортизированно O(α(n)) вместе с union by rank.
Память: O(1).
Корректность: корень не меняется при сжатии; переподвешивание узлов к корню
сохраняет принадлежность классу и укорачивает будущие пути.

Варианты сжатия. Полное сжатие (все к корню) и деление пути (path halving: каждый узел указывает на дедушку) дают одинаковый порядок сложности; деление проще реализовать в один проход.

Алгоритм Find-Set-Path-Halving(x)
1  while parent[x] ≠ x
2      parent[x] ← parent[parent[x]]    # x указывает на дедушку
3      x ← parent[x]
4  return x

Сложность: та же амортизированная O(α(n)); const меньше на коротких путях.

Крайние случаи. Find корня — немедленный возврат. Рекурсивный Find может переполнить стек на длинной цепи; используйте итеративный вариант.

См. рис. 3: путь до и после сжатия.

Рис. 3. Во время Find узлы пути переподвешиваются прямо к корню; следующий Find тех же узлов идёт за [math]\displaystyle{ O(1) }[/math].

Операция: объединить множества (Union)

Идея. Найти корни обоих классов; если они разные, подвесить корень с меньшим рангом (размером) под корень с большим. Это не даёт высоте дерева расти быстрее логарифма.

Пошаговое описание.

rx ← Find-Set(x), ry ← Find-Set(y).
Если rx = ry — ничего не делать (уже один класс).
Иначе подвесить корень меньшего дерева под корень большего.
При равенстве рангов увеличить ранг нового корня.

Инвариант. rank[root] — верхняя оценка высоты дерева; у дерева ранга [math]\displaystyle{ r }[/math] не менее [math]\displaystyle{ 2^r }[/math] узлов, поэтому высота не превосходит [math]\displaystyle{ \log_2 n }[/math].

Псевдокод.

Алгоритм Union(x, y)
Вход:  x, y — элементы
Выход: два класса объединены (если были разными)
1  rx ← Find-Set(x)
2  ry ← Find-Set(y)
3  if rx = ry
4      return
5  if rank[rx] < rank[ry]
6      swap(rx, ry)
7  parent[ry] ← rx
8  if rank[rx] = rank[ry]
9      rank[rx] ← rank[rx] + 1

Сложность: два Find плюс O(1). Без сжатия — O(log n); со сжатием — аморт. O(α(n)).
Корректность: подвешивание корня под корень заменяет два дерева одним, не меняя
разбиение; ранг сохраняет логарифмическую высоту.

Вариант union by size вместо rank: сравнивать число узлов size[] и подвешивать меньшее под большее. Обе метрики равнозначны по сложности; size удобнее, когда нужен ещё и размер класса.

Крайние случаи. Объединение элемента с самим собой — no-op. Неверный swap (подвесить большое под маленькое) ломает оценку высоты.

См. рис. 4: наивное объединение и union by rank.

Рис. 4. Подвешивание меньшего дерева под большее сохраняет высоту [math]\displaystyle{ O(\log n) }[/math]; наивный порядок вырождает дерево в цепь.

Вариант: взвешенный DSU (потенциалы)

Идея. Каждый узел хранит weight[x] — чётность (XOR) от [math]\displaystyle{ x }[/math] до parent[x]. Find вычисляет XOR весов вдоль пути к корню, а Union выставляет вес так, чтобы отношение между любыми двумя вершинами было согласовано. Так DSU умеет проверять чётность отношений и двудольность графа. Для амортизированной оценки вместе со сжатием используется union by size.

Алгоритм Weighted-Find(x)                 # возвращает (корень, XOR весов до корня)
1  if parent[x] = x
2      return (x, 0)
3  (root, w) ← Weighted-Find(parent[x])
4  weight[x] ← weight[x] ⊕ w              # XOR до корня
5  parent[x] ← root                       # сжатие пути
6  return (root, weight[x])

Алгоритм Weighted-Union(x, y, d)           # известно, что parity(x, y) = d
1  (rx, wx) ← Weighted-Find(x)
2  (ry, wy) ← Weighted-Find(y)
3  if rx = ry
4      if (wx ⊕ wy) ≠ d
5          error "противоречие чётности"
6      return
7  if size[rx] < size[ry]
8      swap(rx, ry);  swap(wx, wy)
9  parent[ry] ← rx
10 weight[ry] ← wx ⊕ wy ⊕ d               # согласование чётностей
11 size[rx] ← size[rx] + size[ry]

Сложность: O(α(n)) амортизированно при union by size и сжатии путей.

Применение. Двудольность: окрашиваем рёбра в чётность 0/1; если для ребра [math]\displaystyle{ (u,v) }[/math] wx ⊕ wy ≠ d, это противоречие — нечётный цикл.

См. рис. 5: веса на рёбрах и проверка чётности.

Рис. 5. Веса до родителя вычисляются через XOR при Find; это позволяет поддерживать чётность отношений и находить противоречия (нечётные циклы).

Вариант: DSU с откатом (rollback)

Идея. Если не применять сжатие путей, Union меняет всего один указатель и одно значение размера. Запоминая изменения в стеке, можно откатить последнее объединение. Это нужно для офлайн-задачи динамической связности (рёбра живут на интервалах времени; обход дерева отрезков с Union на входе и Rollback на выходе).

Алгоритм Union-Rollback(x, y)              # union by size, без сжатия
1  rx ← Find(x);  ry ← Find(y)
2  if rx = ry
3      return false
4  if size[rx] < size[ry]  swap(rx, ry)
5  история.добавить((ry, rx, parent[ry], size[rx]))   # для отката
6  parent[ry] ← rx
7  size[rx] ← size[rx] + size[ry]
8  return true

Алгоритм Rollback()
1  (ry, rx, oldParent, oldSize) ← история.взять()
2  parent[ry] ← oldParent
3  size[rx] ← oldSize

Сложность: O(log n) без сжатия; откат — O(1).

Важно. Сжатие путей необратимо, поэтому в rollback-варианте его не применяют; union by size сам по себе даёт [math]\displaystyle{ O(\log n) }[/math].

См. рис. 6: стек изменений и откат.

Рис. 6. Без сжатия Union обратим: стек изменений позволяет Rollback за [math]\displaystyle{ O(1) }[/math], что используют в офлайн-связности.

Реализация на C++

Классический DSU с объединением по размеру и итеративным сжатием путей. Метод find — итеративный (без риска переполнения стека); unite возвращает true, если множества были разными.

#include <iostream>
#include <vector>
#include <numeric>
#include <utility>
#include <cassert>

class DSU {
    std::vector<int> parent_, size_;
public:
    explicit DSU(int n) : parent_(n), size_(n, 1) {
        std::iota(parent_.begin(), parent_.end(), 0);   // каждый — сам себе родитель
    }

    int find(int x) {                                   // сжатие путей, итеративно
        int root = x;
        while (parent_[root] != root) root = parent_[root];
        while (parent_[x] != root) {
            int next = parent_[x];
            parent_[x] = root;
            x = next;
        }
        return root;
    }

    bool unite(int a, int b) {                           // union by size
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (size_[a] < size_[b]) std::swap(a, b);
        parent_[b] = a;
        size_[a] += size_[b];
        return true;
    }

    bool connected(int a, int b) { return find(a) == find(b); }
    int size(int x) { return size_[find(x)]; }
};

int main() {
    DSU dsu(6);

    // классы эквивалентности
    assert(!dsu.connected(0, 5));
    dsu.unite(0, 1);
    dsu.unite(2, 3);
    dsu.unite(1, 2);
    assert(dsu.connected(0, 3));
    assert(!dsu.connected(0, 4));
    assert(dsu.size(0) == 4);

    // компоненты связности графа: ребро (u, v) сливает компоненты
    DSU comps(5);
    std::vector<std::pair<int,int>> edges = {{0,1},{1,2},{3,4}};
    int components = 5;
    for (auto [u, v] : edges)
        if (comps.unite(u, v)) --components;      // объединение уменьшает число компонент
    assert(components == 2);

    std::cout << "ok\n";
    return 0;
}

Замечания по реализации.

Читайте size только у корня, то есть после find(x); размер некорневого узла не поддерживается.
Для взвешенного DSU добавьте массив weight[] и пересчитывайте веса при Union (см. раздел «Вариант: взвешенный DSU (потенциалы)»).
Для отката используйте size без сжатия и стек изменений (см. раздел «Вариант: DSU с откатом (rollback)»).

Сводная таблица сложности

Реализация	`Find`	`Union`	Последовательность [math]\displaystyle{ m }[/math] операций	Память
Наивно (лес без оптимизаций)	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(mn) }[/math]	[math]\displaystyle{ O(n) }[/math]
Union by rank/size	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(m\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]
Сжатие путей	[math]\displaystyle{ O(\log n) }[/math] аморт.	[math]\displaystyle{ O(\log n) }[/math] аморт.	[math]\displaystyle{ O((m+n)\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]
Union by rank + сжатие	[math]\displaystyle{ O(\alpha(n)) }[/math] аморт.	[math]\displaystyle{ O(\alpha(n)) }[/math] аморт.	[math]\displaystyle{ O(m\,\alpha(n)) }[/math]	[math]\displaystyle{ O(n) }[/math]
Взвешенный DSU	[math]\displaystyle{ O(\alpha(n)) }[/math] аморт.	[math]\displaystyle{ O(\alpha(n)) }[/math] аморт.	[math]\displaystyle{ O(m\,\alpha(n)) }[/math]	[math]\displaystyle{ O(n) }[/math]
DSU с откатом (без сжатия)	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(m\log n) }[/math]	[math]\displaystyle{ O(n)+O(m) }[/math] стек

Примечание. Амортизированная оценка [math]\displaystyle{ O(\alpha(n)) }[/math] относится к последовательности операций и не гарантирует константу на отдельную операцию. Нижняя граница Тарджана [math]\displaystyle{ \Omega(\alpha(n)) }[/math] показывает, что эта оценка точна в стандартной модели union–find. См. рис. 7: сравнение оценок.

Рис. 7. От [math]\displaystyle{ O(n) }[/math] у наивной реализации до [math]\displaystyle{ O(\alpha(n)) }[/math] при обеих оптимизациях; [math]\displaystyle{ \alpha(n) \le 4 }[/math] для всех практических [math]\displaystyle{ n }[/math], тогда как [math]\displaystyle{ \log_2 n }[/math] достигает десятков.

Трассировка примера

Пять элементов, parent = [0,1,2,3,4], size = [1,1,1,1,1]. Применяем union by size и сжатие.

Шаг	Операция	Действие	`parent` после сжатия	`size` корня
0	—	исходно все отдельны	[0,1,2,3,4]	все 1
1	`Union(0,1)`	размеры равны → `parent[1]=0`	[0,0,2,3,4]	size[0]=2
2	`Union(2,3)`	`parent[3]=2`	[0,0,2,2,4]	size[2]=2
3	`Union(0,2)`	равны (2=2) → `parent[2]=0`	[0,0,0,2,4]	size[0]=4
4	`Find(3)`	путь 3→2→0, сжатие: `parent[3]=0`	[0,0,0,0,4]	—
5	`Union(4,0)`	`parent[4]=0`	[0,0,0,0,0]	size[0]=5
6	`Find(4)`	4→0, уже коротко	[0,0,0,0,0]	—

После шага 4 цепочка 3→2→0 сжата до 3→0: следующий Find(3) выполняется за один шаг. Все элементы в итоге в одном классе с представителем 0.

Корректность и оценка сложности

Лемма 1 (инвариант разбиения). В любой момент parent задаёт лес, корни которого — представители классов, а классы образуют разбиение множества элементов.

Доказательство. Индукция по операциям. Make-Set создаёт корректное одноэлементное дерево. Find не меняет разбиение. Union подвешивает корень одного дерева под корень другого, заменяя два дерева одним; разбиение остаётся корректным. [math]\displaystyle{ \blacksquare }[/math]

Лемма 2 (граница высоты при union by rank). Дерево ранга [math]\displaystyle{ r }[/math] содержит не менее [math]\displaystyle{ 2^r }[/math] узлов, а его высота не превосходит [math]\displaystyle{ r }[/math]. Следовательно, высота дерева из [math]\displaystyle{ n }[/math] узлов — [math]\displaystyle{ O(\log n) }[/math].

Доказательство. Индукция по числу Union. Ранг растёт только при объединении двух деревьев равного ранга, каждое из которых по предположению имеет [math]\displaystyle{ \ge 2^r }[/math] узлов; объединённое дерево — [math]\displaystyle{ \ge 2^{r+1} }[/math] узлов. Значит, узел ранга [math]\displaystyle{ r }[/math] стоит над [math]\displaystyle{ \ge 2^r }[/math] узлами, откуда [math]\displaystyle{ 2^r \le n }[/math] и [math]\displaystyle{ r \le \log_2 n }[/math]. [math]\displaystyle{ \blacksquare }[/math]

Теорема 3 (сложность). Последовательность из [math]\displaystyle{ m }[/math] операций Make-Set, Find и Union над [math]\displaystyle{ n }[/math] элементами при union by rank и сжатии путей выполняется за [math]\displaystyle{ O(m\,\alpha(n)) }[/math] амортизированно.

Доказательство (эскиз). Идея — ввести потенциал, зависящий от «ранга пути» узлов, и показать, что Find длинной цепочки оплачивается предшествующими Union, которые её «вырастили». Каждый Union повышает потенциал структуры незначительно, а Find его понижает сжатием. Полный бухгалтерский учёт даёт оценку [math]\displaystyle{ O(m\,\alpha(n)) }[/math]; точное доказательство — у Тарджана. [math]\displaystyle{ \blacksquare }[/math]

Нижняя граница. Тарджан доказал, что существует последовательность операций, требующая [math]\displaystyle{ \Omega(m\,\alpha(n)) }[/math] времени, поэтому [math]\displaystyle{ O(\alpha(n)) }[/math] — асимптотически оптимальная оценка.

Взвешенный DSU. Инвариант: XOR весов от [math]\displaystyle{ x }[/math] до корня равен отношению (например, чётности) между [math]\displaystyle{ x }[/math] и представителем класса. Union выставляет вес нового ребра к корню так, чтобы это равенство сохранилось; Find вычисляет XOR весов и сжимает путь. Корректность — индукция по операциям.

Сравнение с альтернативами

Подход	`Union`	`Find`	Откат	Порядковые запросы	Когда выбирать
Связный список	[math]\displaystyle{ O(1) }[/math]/ [math]\displaystyle{ O(\text{size}) }[/math]	[math]\displaystyle{ O(1) }[/math] (метка)	сложно	нет	почти не используют
DSU (ранг + сжатие)	[math]\displaystyle{ O(\alpha(n)) }[/math]	[math]\displaystyle{ O(\alpha(n)) }[/math]	нет	нет	объединения + проверка связности
Взвешенный DSU	[math]\displaystyle{ O(\alpha(n)) }[/math]	[math]\displaystyle{ O(\alpha(n)) }[/math]	нет	нет	чётность, двудольность, смещения
DSU с откатом	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	да	нет	офлайн-связность, обход отрезков
Сбалансированное BST	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	да (персистентно)	да	нужны порядковые/диапазонные запросы
Персистентный DSU	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	да (версии)	нет	запросы к историческим версиям

Вердикт. Для «объединяй и проверяй связность» DSU вне конкуренции: простая, компактная и практически константная. Если нужны чётности — взвешенный DSU; если откат — DSU без сжатия со стеком; если порядковая статистика или разбиение — обычный DSU не подходит.

Вариант: персистентный DSU

Идея. Обычный DSU разрушает прошлое: Union и сжатие путей меняют массив parent навсегда. Персистентная версия сохраняет все прошлые состояния, так что запрос Find(version, x) может обратиться к любой исторической версии, не портя более поздние.

Как хранить версии.

Path copying. При Union копируется не весь массив, а лишь изменённые узлы вдоль одного пути: новую версию образуют общие (неизменные) части старых деревьев и скопированный путь.
Fat nodes. У каждого узла хранится список пар «(версия, значение)», что позволяет читать значение на любой версии.
Union by rank без сжатия. Сжатие путей необратимо, поэтому в персистентном DSU его не применяют; объединение по рангу даёт [math]\displaystyle{ O(\log n) }[/math] и легко версионируется.

Алгоритм Persistent-Union(version, x, y)      # создаёт version + 1
1  rx ← Persistent-Find(version, x)
2  ry ← Persistent-Find(version, y)
3  if rx = ry
4      return version                         # изменений нет — версия та же
5  if rank[version][rx] < rank[version][ry]
6      swap(rx, ry)
7  # path copying: изменяются parent[ry] и, при равенстве рангов, rank[rx]
8  parent[version+1][ry] ← rx              # остальные записи общие
9  rank[version+1]   ← rank[version]
10 if rank[version][rx] = rank[version][ry]
11     rank[version+1][rx] ← rank[version][rx] + 1
12 return version + 1

Сложность: O(log n) на операцию без сжатия; память O(n + число изменений).
Корректность: новая версия отличается от старой только вдоль изменённого пути;
множества всех прежних версий остаются неизменными.

Применение. Запросы к истории версий (например, «были ли связны [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math] в момент [math]\displaystyle{ t }[/math]»), откат в поиске с возвратом, доказательства и унификация в SMT. Отличие от DSU с откатом ([math]\displaystyle{ O(1) }[/math] на Rollback, но откат идёт по принципу LIFO в текущей ветке): персистентный DSU даёт доступ к произвольной версии.

См. рис. 8: path copying и общие узлы версий.

Рис. 8. Персистентный DSU использует path copying: новая версия разделяет неизменные узлы со старой и копирует только изменённый путь; Find(version, x) читает нужную версию. Сжатие путей здесь неприменимо.

Где применяется

Алгоритм Краскала. Проверка «не образует ли ребро цикл» — это Find(u) ≠ Find(v), а слияние компонент — Union. DSU делает Краскала линейным по числу рёбер после сортировки [1].
Компоненты связности и детекция циклов. Добавляя рёбра неориентированного графа и объединяя компоненты, легко считать число компонент и находить моменты появления циклов [1].
Классы эквивалентности. Любое отношение эквивалентности, задаваемое парами «слить», — типичная нагрузка DSU [1].
Офлайн-динамическая связность. DSU с откатом и дерево отрезков по времени отвечают на запросы связности при рёбрах, живущих на интервалах [8].
LCA Тарджана (офлайн). Обход в глубину с DSU позволяет находить наименьших общих предков для набора запросов за почти линейное время [7].
Проверка ограничений и двудольности. Взвешенный DSU (потенциалы) распознаёт несовместные отношения и нечётные циклы — например, при проверке двудольности или расписаний [5].
Обработка изображений и перколяция. Компоненты «связанных» пикселей объединяются DSU; при перколяции им проверяют протекание решётки [6].
Унификация в компиляторах и SMT. Понятия «объединить два класса» и «найти представителя» лежат в основе алгоритмов унификации типов и решателей равенств [5].

Применение: офлайн-динамическая связность

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

Пошаговое описание.

Каждое ребро со временем жизни [math]\displaystyle{ [\ell, r] }[/math] разложить по [math]\displaystyle{ O(\log T) }[/math] каноническим узлам дерева отрезков.
Обходить дерево в глубину: войдя в узел — выполнить Union-Rollback всех закреплённых за ним рёбер и запомнить изменения.
Дойдя до листа (момент времени [math]\displaystyle{ t }[/math]) — ответить на запросы связности для этого [math]\displaystyle{ t }[/math].
Выходя из узла — Rollback сделанных объединений.

Rollback возможен только потому, что в этой задаче не применяют сжатие путей (union by size без сжатия).

Алгоритм Dynamic-Connectivity(node, t-range)
1  count ← 0
2  for each ребро e, закреплённое за node
3      if Union-Rollback(e.u, e.v)              # реально слило компоненты
4          ++count
5  if node — лист (момент t)
6      для каждого запроса (u, v) в t
7          ответ ← Connected(u, v)
8  else
9      рекурсивно обработать левого и правого ребёнка
10 Rollback ровно count объединений              # восстановить состояние

Сложность: O(m log T log n + q log n) времени, O(m log T) памяти.
Корректность: к моменту ответа в листе DSU содержит ровно рёбра, активные в момент t.

Online-альтернатива. Для произвольных добавлений и удалений (online) DSU не годится: для леса применяют Euler Tour Trees или Link-Cut Trees за [math]\displaystyle{ O(\log n) }[/math], а для общего графа нужны более сложные динамические структуры.

См. рис. 9: интервалы рёбер и дерево отрезков.

Рис. 9. Рёбра, живущие на интервалах, раскладываются по дереву отрезков; обход с Union/Rollback даёт ответы в каждый момент времени.

Применение: офлайн LCA Тарджана

Идея. Набор запросов «наименьший общий предок (LCA) для [math]\displaystyle{ (u, v) }[/math]» решается офлайн за почти линейное время обходом дерева с DSU. Завершённые поддеревья объединяются с родителем; представителю множества приписывается текущий предок.

Пошаговое описание.

Make-Set(u); ancestor[Find(u)] ← u.
Для каждого ребёнка [math]\displaystyle{ v }[/math]: рекурсивно Tarjan-LCA(v), затем Union(u, v) и ancestor[Find(u)] ← u.
Пометить [math]\displaystyle{ u }[/math] завершённой (чёрной).
Для каждого запроса [math]\displaystyle{ (u, w) }[/math], где [math]\displaystyle{ w }[/math] уже завершён: LCA(u, w) ← ancestor[Find(w)].

Алгоритм Tarjan-LCA(u)
1  Make-Set(u)
2  ancestor[Find(u)] ← u
3  for each ребёнок v вершины u
4      Tarjan-LCA(v)
5      Union(u, v)
6      ancestor[Find(u)] ← u
7  color[u] ← black
8  for each запрос (u, w) с color[w] = black
9      ответ(u, w) ← ancestor[Find(w)]

Сложность: O((n + q) α(n)) амортизированно (n — вершины, q — запросы).
Корректность: к моменту, когда w завершена, а u обрабатывается, множеством w управляет
ближайший общий предок u и w, и ancestor даёт именно его.

Разбор на примере (рис. 10). Дерево: 1 → {2, 3}, 2 → {4, 5}, 3 → {6}. Обход preorder: 1→2→4→5→3→6; завершение (postorder): 4, 5, 2, 6, 3, 1. Запросы: (4, 5) и (5, 6). При завершении 4 делаем Union(2, 4); при обработке 5 запрос (4, 5) даёт ancestor[Find(4)] = 2. При завершении 2 — Union(1, 2). При обработке 6 запрос (5, 6) даёт ancestor[Find(5)] = 1. Ответы: (4,5) → 2, (5,6) → 1.

Рис. 10. LCA Тарджана: завершённые поддеревья объединены с родителями; запрос к завершённой вершине возвращает ancestor[Find(w)] — её LCA с текущей.

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

1964. Б. Галлер и М. Фишер описали структуру union–find и отметили важность балансировки [2].
1975. Р. Тарджан строго проанализировал сжатие путей и union by rank и доказал амортизированную оценку [math]\displaystyle{ O(\alpha(n)) }[/math], а также нижнюю границу [3]. Это одна из первых работ по амортизационному анализу.
1984. Тарджан и ван Леувен исследовали варианты сжатия путей (path halving, path splitting) и уточнили оценки [4].
Название «union–find» отражает две главные операции; аббревиатура DSU — от disjoint-set union (объединение непересекающихся множеств).

Типичные ошибки и подводные камни

Забыть сжатие путей или объединение по рангу. Одна оптимизация даёт лишь [math]\displaystyle{ O(\log n) }[/math]; только вдвоём они достигают [math]\displaystyle{ O(\alpha(n)) }[/math].
Неверный union by rank/size. Подвешивание большого дерева под маленькое вырождает лес в цепь и портит оценку.
Рекурсивный find на длинной цепи. Может переполнить стек; итеративный вариант безопаснее.
Перепутать parent и rank/size. Массивы имеют разные смыслы; size хранится только у корня (или некорректно читается после сжатия).
Пытаться разбить множество (Split). Обычный DSU этого не умеет: операции необратимы.
Сжатие путей в задаче с откатом. Сжатие необратимо; для rollback используют union by size без сжатия.
Индексация с 0/1. Убедитесь, что parent инициализируется самими индексами, а диапазон согласован с вершинами графа.
Забыть, что DSU — не для удалений. Динамические удаления рёбер обычным DSU не поддерживаются (нужны откат или другие структуры).
Смешение уровней. find(x) возвращает представителя, а не «родителя»; не стоит использовать parent[x] напрямую как класс.
Потеря весов в взвешенном DSU. При Union нужно корректно пересчитать вес нового ребра, иначе чётности «разъедутся».

Задачи для практики

Реализация. Реализуйте DSU с обеими оптимизациями; измерьте среднее число шагов на [math]\displaystyle{ 10^6 }[/math] операций. Подсказка: должно быть близко к константе.
Число компонент. По списку рёбер найдите число компонент связности. Подсказка: начинайте с [math]\displaystyle{ n }[/math] и уменьшайте при каждом успешном Union.
Циклы. Определите, содержит ли неориентированный граф цикл. Подсказка: ребро [math]\displaystyle{ (u,v) }[/math] с Find(u)=Find(v) даёт цикл.
Взвешенный DSU. Проверьте двудольность графа через чётности. Подсказка: противоречие возникает при нечётном цикле.
Офлайн-связность. Для рёбер, живущих на интервалах времени, ответьте на запросы связности. Подсказка: дерево отрезков по времени + Union/Rollback.
LCA Тарджана. Найдите LCA для набора запросов офлайн. Подсказка: обход DFS, Union к родителю при выходе из поддерева.
Краскал. Примените DSU в MST и сравните с Примом. Подсказка: Find(u) ≠ Find(v).
Без оптимизаций. Постройте последовательность Union, при которой дерево вырождается в цепь длины [math]\displaystyle{ n }[/math], и покажите, что следующий Find стоит [math]\displaystyle{ \Theta(n) }[/math]. Сравните с union by rank.

Связанные темы

Алгоритм Краскала — основной потребитель DSU.
Алгоритм Прима — альтернативный алгоритм MST.
Графы — компоненты связности и обходы.
Асимптотическая сложность — нотация [math]\displaystyle{ O }[/math], [math]\displaystyle{ \Omega }[/math] и обратная функция Аккермана.

Источники

Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 21 «Data Structures for Disjoint Sets».
Galler B. A., Fischer M. J. An Improved Equivalence Algorithm // Communications of the ACM. — 1964. — Vol. 7, No. 5. — P. 301–303.
Tarjan R. E. Efficiency of a Good But Not Linear Set Union Algorithm // Journal of the ACM. — 1975. — Vol. 22, No. 2. — P. 215–225.
Tarjan R. E., van Leeuwen J. Worst-Case Analysis of Set Union Algorithms // Journal of the ACM. — 1984. — Vol. 31, No. 2. — P. 245–281.
Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — §1.5 «Case Study: Union-Find».
Wikipedia: Disjoint-set data structure. URL: https://en.wikipedia.org/wiki/Disjoint-set_data_structure.
Tarjan R. E. Applications of Path Compression on Balanced Trees // Journal of the ACM. — 1979. — Vol. 26, No. 4. — P. 690–715.
cp-algorithms: Disjoint Set Union. URL: https://cp-algorithms.com/data_structures/disjoint_set_union.html.

Поиск

Навигация

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

Содержание

TL;DR

Инфобокс

Определения

Мотивация и интуиция

Устройство

Операции и алгоритмы

Операция: создать множество (Make-Set)

Операция: найти представителя (Find-Set)

Операция: объединить множества (Union)

Вариант: взвешенный DSU (потенциалы)

Вариант: DSU с откатом (rollback)

Реализация на C++

Сводная таблица сложности

Трассировка примера

Корректность и оценка сложности

Сравнение с альтернативами

Вариант: персистентный DSU

Где применяется

Применение: офлайн-динамическая связность

Применение: офлайн LCA Тарджана

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

Типичные ошибки и подводные камни

Задачи для практики

Связанные темы

Источники