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

== TL;DR ==

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


== Инфобокс ==

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


== Определения ==

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

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

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

{| class="wikitable"
|-
! Операция
! Смысл
! Постусловие
|-
| <code>Make-Set(x)</code>
| создать новое множество <math>\{x\}</math>
| <math>x</math> — отдельный класс, представитель <math>x</math>
|-
| <code>Find-Set(x)</code>
| представитель класса <math>x</math>
| <code>Find-Set(x) = Find-Set(y)</code> ⟺ <math>x, y</math> в одном классе
|-
| <code>Union(x, y)</code>
| слить классы <math>x</math> и <math>y</math>
| два класса заменены их объединением
|}

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

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

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

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

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

[[Файл:dsu-01-adt.svg|thumb|700px|Рис. 1. DSU хранит разбиение на непересекающиеся множества и поддерживает <code>Make-Set</code>, <code>Find-Set</code>, <code>Union</code>. Разбиение обратно не поддерживается.]]


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

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

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

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

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


== Устройство ==

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

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

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

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

[[Файл:dsu-02-representations.svg|thumb|700px|Рис. 2. Связный список даёт <math>O(1)</math> слияние, но дорогое обновление представителя; лес даёт <math>O(1)</math> слияние ценой пути к корню, который и укорачивают оптимизациями.]]


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


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

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

<syntaxhighlight lang="text">Алгоритм Make-Set(x)
1  parent[x] ← x
2  rank[x] ← 0          # или size[x] ← 1

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

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

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

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

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

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

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

<syntaxhighlight lang="text">Алгоритм 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).
Корректность: корень не меняется при сжатии; переподвешивание узлов к корню
сохраняет принадлежность классу и укорачивает будущие пути.</syntaxhighlight>
'''Варианты сжатия.''' Полное сжатие (все к корню) и '''деление пути''' (path halving: каждый узел указывает на дедушку) дают одинаковый порядок сложности; деление проще реализовать в один проход.

<syntaxhighlight lang="text">Алгоритм 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 меньше на коротких путях.</syntaxhighlight>
'''Крайние случаи.''' <code>Find</code> корня — немедленный возврат. Рекурсивный <code>Find</code> может переполнить стек на длинной цепи; используйте итеративный вариант.

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

[[Файл:dsu-03-path-compression.svg|thumb|700px|Рис. 3. Во время <code>Find</code> узлы пути переподвешиваются прямо к корню; следующий <code>Find</code> тех же узлов идёт за <math>O(1)</math>.]]


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

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

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

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

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

'''Псевдокод.'''

<syntaxhighlight lang="text">Алгоритм 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)).
Корректность: подвешивание корня под корень заменяет два дерева одним, не меняя
разбиение; ранг сохраняет логарифмическую высоту.</syntaxhighlight>
Вариант '''union by size''' вместо rank: сравнивать число узлов <code>size[]</code> и подвешивать меньшее под большее. Обе метрики равнозначны по сложности; <code>size</code> удобнее, когда нужен ещё и размер класса.

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

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

[[Файл:dsu-04-union-by-rank.svg|thumb|700px|Рис. 4. Подвешивание меньшего дерева под большее сохраняет высоту <math>O(\log n)</math>; наивный порядок вырождает дерево в цепь.]]


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

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

<syntaxhighlight lang="text">Алгоритм 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 и сжатии путей.</syntaxhighlight>
'''Применение.''' Двудольность: окрашиваем рёбра в чётность 0/1; если для ребра <math>(u,v)</math> <code>wx ⊕ wy ≠ d</code>, это противоречие — нечётный цикл.

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

[[Файл:dsu-05-weighted.svg|thumb|700px|Рис. 5. Веса до родителя вычисляются через XOR при <code>Find</code>; это позволяет поддерживать чётность отношений и находить противоречия (нечётные циклы).]]


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

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

<syntaxhighlight lang="text">Алгоритм 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).</syntaxhighlight>
'''Важно.''' Сжатие путей необратимо, поэтому в rollback-варианте его не применяют; union by size сам по себе даёт <math>O(\log n)</math>.

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

[[Файл:dsu-06-rollback.svg|thumb|700px|Рис. 6. Без сжатия <code>Union</code> обратим: стек изменений позволяет <code>Rollback</code> за <math>O(1)</math>, что используют в офлайн-связности.]]


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

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

<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>
'''Замечания по реализации.'''

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


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

{| class="wikitable"
|-
! Реализация
! <code>Find</code>
! <code>Union</code>
! Последовательность <math>m</math> операций
! Память
|-
| Наивно (лес без оптимизаций)
| <math>O(n)</math>
| <math>O(n)</math>
| <math>O(mn)</math>
| <math>O(n)</math>
|-
| Union by rank/size
| <math>O(\log n)</math>
| <math>O(\log n)</math>
| <math>O(m\log n)</math>
| <math>O(n)</math>
|-
| Сжатие путей
| <math>O(\log n)</math> аморт.
| <math>O(\log n)</math> аморт.
| <math>O((m+n)\log n)</math>
| <math>O(n)</math>
|-
| '''Union by rank + сжатие'''
| <math>O(\alpha(n))</math> аморт.
| <math>O(\alpha(n))</math> аморт.
| <math>O(m\,\alpha(n))</math>
| <math>O(n)</math>
|-
| Взвешенный DSU
| <math>O(\alpha(n))</math> аморт.
| <math>O(\alpha(n))</math> аморт.
| <math>O(m\,\alpha(n))</math>
| <math>O(n)</math>
|-
| DSU с откатом (без сжатия)
| <math>O(\log n)</math>
| <math>O(\log n)</math>
| <math>O(m\log n)</math>
| <math>O(n)+O(m)</math> стек
|}

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

[[Файл:dsu-07-complexity.svg|thumb|700px|Рис. 7. От <math>O(n)</math> у наивной реализации до <math>O(\alpha(n))</math> при обеих оптимизациях; <math>\alpha(n) \le 4</math> для всех практических <math>n</math>, тогда как <math>\log_2 n</math> достигает десятков.]]


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

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

{| class="wikitable"
|-
! Шаг
! Операция
! Действие
! <code>parent</code> после сжатия
! <code>size</code> корня
|-
| 0
| —
| исходно все отдельны
| [0,1,2,3,4]
| все 1
|-
| 1
| <code>Union(0,1)</code>
| размеры равны → <code>parent[1]=0</code>
| [0,0,2,3,4]
| size[0]=2
|-
| 2
| <code>Union(2,3)</code>
| <code>parent[3]=2</code>
| [0,0,2,2,4]
| size[2]=2
|-
| 3
| <code>Union(0,2)</code>
| равны (2=2) → <code>parent[2]=0</code>
| [0,0,0,2,4]
| size[0]=4
|-
| 4
| <code>Find(3)</code>
| путь 3→2→0, сжатие: <code>parent[3]=0</code>
| [0,0,0,0,4]
| —
|-
| 5
| <code>Union(4,0)</code>
| <code>parent[4]=0</code>
| [0,0,0,0,0]
| size[0]=5
|-
| 6
| <code>Find(4)</code>
| 4→0, уже коротко
| [0,0,0,0,0]
| —
|}

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


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

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

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

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

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

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

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

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

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


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

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

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


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

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

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

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

<syntaxhighlight lang="text">Алгоритм 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 + число изменений).
Корректность: новая версия отличается от старой только вдоль изменённого пути;
множества всех прежних версий остаются неизменными.</syntaxhighlight>
'''Применение.''' Запросы к истории версий (например, «были ли связны <math>u</math> и <math>v</math> в момент <math>t</math>»), откат в поиске с возвратом, доказательства и унификация в SMT. Отличие от DSU с откатом (<math>O(1)</math> на <code>Rollback</code>, но откат идёт по принципу LIFO в текущей ветке): персистентный DSU даёт доступ к '''произвольной''' версии.

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

[[Файл:dsu-08-persistent.svg|thumb|700px|Рис. 8. Персистентный DSU использует path copying: новая версия разделяет неизменные узлы со старой и копирует только изменённый путь; <code>Find(version, x)</code> читает нужную версию. Сжатие путей здесь неприменимо.]]


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

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


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

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

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

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

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

<syntaxhighlight lang="text">Алгоритм 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.</syntaxhighlight>
'''Online-альтернатива.''' Для произвольных добавлений и удалений (online) DSU не годится: для леса применяют Euler Tour Trees или Link-Cut Trees за <math>O(\log n)</math>, а для общего графа нужны более сложные динамические структуры.

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

[[Файл:dsu-09-dynamic-connectivity.svg|thumb|700px|Рис. 9. Рёбра, живущие на интервалах, раскладываются по дереву отрезков; обход с <code>Union</code>/<code>Rollback</code> даёт ответы в каждый момент времени.]]


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

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

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

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

<syntaxhighlight lang="text">Алгоритм 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 даёт именно его.</syntaxhighlight>
'''Разбор на примере (рис. 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 делаем <code>Union(2, 4)</code>; при обработке 5 запрос (4, 5) даёт <code>ancestor[Find(4)] = 2</code>. При завершении 2 — <code>Union(1, 2)</code>. При обработке 6 запрос (5, 6) даёт <code>ancestor[Find(5)] = 1</code>. Ответы: <code>(4,5) → 2</code>, <code>(5,6) → 1</code>.

[[Файл:dsu-10-tarjan-lca.svg|thumb|700px|Рис. 10. LCA Тарджана: завершённые поддеревья объединены с родителями; запрос к завершённой вершине возвращает <code>ancestor[Find(w)]</code> — её LCA с текущей.]]


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

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


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

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


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

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


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

* [[Алгоритм Краскала]] — основной потребитель DSU.
* [[Алгоритм Прима]] — альтернативный алгоритм MST.
* [[Графы]] — компоненты связности и обходы.
* [[Асимптотическая сложность]] — нотация <math>O</math>, <math>\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: <nowiki>https://en.wikipedia.org/wiki/Disjoint-set_data_structure</nowiki>.
# 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: <nowiki>https://cp-algorithms.com/data_structures/disjoint_set_union.html</nowiki>.

[[Category:Алгоритмы и структуры данных]]