Структуры данных Система непересекающихся множеств (DSU)
0%

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

16 мин 3329 слов
#структуры данных#dsu#графы#амортизированный анализ

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

Задача, из которой всё выросло

Представьте социальную сеть, в которой есть только одно действие — «подружить A и B», и один вопрос — «знакомы ли A и B хотя бы через цепочку общих друзей». Или сеть дорог, куда постепенно добавляют трассы, а нужно знать, можно ли доехать из города X в город Y. Или процесс кластеризации, где на каждом шаге две группы сливаются в одну.

Все три постановки — это одна и та же задача динамической связности в режиме только добавления рёбер (incremental connectivity). Формально мы поддерживаем разбиение множества {0, 1, ..., n−1} на непересекающиеся подмножества и обслуживаем две операции:

  • union(a, b) — объединить множества, содержащие a и b;
  • find(a) — вернуть канонический идентификатор (представителя) множества, содержащего a.

Вопрос «связаны ли a и b» — это просто find(a) == find(b).

Структура данных, которая это делает, называется системой непересекающихся множеств, union-find или DSU (disjoint set union). Её ценность в том, что при правильной реализации амортизированная стоимость операции — O(α(n)), где α — обратная функция Аккермана, которая для любого мыслимого n не превышает 4. То есть практически константа, при затратах памяти в два целочисленных массива.

Почему нельзя решить задачу «в лоб»? Можно — но плохо. Если каждый раз запускать поиск в ширину по графу (см. https://courses.digitable.life/post/data-structures/10-graphs-representation/), запрос стоит O(V + E). Если хранить у каждого элемента метку кластера, find мгновенный, но union требует перекрасить целое множество — O(n) на операцию. DSU — это изящный компромисс, который бьёт оба наивных подхода.

Интуиция: лес представителей

Ключевая идея (Galler и Fischer, 1964, «An improved equivalence algorithm»): каждое множество хранится как дерево, направленное к корню. У каждого элемента есть указатель на «родителя»; корень указывает сам на себя и служит представителем множества.

  • find(x) — идти по указателям вверх, пока не упрёмся в корень.
  • union(a, b) — найти оба корня и подвесить один под другой. Одна запись в память.

Аналогия: организация с иерархией начальников. Чтобы понять, в одной ли компании работают два человека, каждый поднимается по цепочке до генерального директора; если директора совпали — компания одна. Слияние компаний — это назначить одного директора подчинённым другого.

Важно: форма дерева не несёт никакого смысла. Она не отражает историю объединений, не задаёт порядок и не является частью ответа. Это чистая служебная структура, и мы имеем полное право деформировать её как угодно, лишь бы сохранялось множество вершин каждого дерева. Именно эта свобода и делает возможными обе оптимизации ниже.

Наивная реализация занимает десять строк — и в худшем случае вырождается в связный список (см. https://courses.digitable.life/post/data-structures/03-linked-lists/), давая O(n) на find. Достаточно последовательно выполнять union(0,1), union(1,2), union(2,3), ..., каждый раз подвешивая старый корень под новый. Поэтому нужны эвристики.

Эвристика 1: объединение по размеру (рангу)

Правило: всегда подвешиваем корень меньшего дерева под корень большего. Вместо размера можно хранить «ранг» — верхнюю оценку высоты, увеличиваемую на 1 при слиянии равных.

Объединение по размеру: меньшее дерево подвешивается к большему

Почему это работает. Глубина узла увеличивается на 1 только тогда, когда его дерево оказалось меньшим в слиянии. Но в этот момент размер дерева, которому он теперь принадлежит, как минимум удваивается. Удвоение можно проделать не более log₂ n раз, значит глубина любого узла — O(log n), и find тоже O(log n) в худшем случае. Уже приемлемо, и, в отличие от следующей эвристики, эта оценка строго худшая, не амортизированная — что критично для вариантов с откатами.

Размер против ранга — практически эквивалентны по скорости. Размер удобнее тем, что его можно спрашивать как полезные данные («сколько элементов в компоненте»), поэтому по умолчанию берите его.

Эвристика 2: сжатие пути

Раз форма дерева нам безразлична, то, пройдя от x до корня, можно переподвесить все узлы этого пути прямо к корню. Один лишний проход — и следующий find для любого из них отработает за один шаг.

Сжатие пути: после find все узлы пути становятся детьми корня

Это классический приём амортизированного анализа (подробнее о методе потенциалов — в https://courses.digitable.life/post/data-structures/01-complexity-and-memory/): дорогая операция «оплачивает» будущие дешёвые. Одна операция может стоить O(log n), но серия из m операций стоит куда меньше, чем m·log n.

Варианты сжатия в один проход

Полное сжатие требует двух проходов по пути. Существуют однопроходные варианты (Tarjan, van Leeuwen, «Worst-case Analysis of Set Union Algorithms», JACM 1984), которые дают ту же асимптотику:

  • path halving — каждый второй узел пути переподвешивается к деду: parent[x] = parent[parent[x]];
  • path splitting — каждый узел пути переподвешивается к своему деду.

На практике path halving часто быстрее полного сжатия: один проход, меньше промахов кэша, отличная предсказуемость ветвлений. Именно его используют в высокопроизводительных реализациях.

Вместе: почти константа

Тарьян в 1975 году доказал («Efficiency of a Good But Not Linear Set Union Algorithm», JACM), что union by rank + path compression дают амортизированную оценку O(α(n)) на операцию, где α — обратная функция Аккермана.

Насколько мала α? Функция Аккермана растёт чудовищно быстро, поэтому её «обратная» растёт чудовищно медленно:

n α(n)
до 2 0
до 4 1
до 8 2
до 2048 3
до 2↑↑2048 (башня степеней двойки высоты 2048) 4

Число атомов в наблюдаемой Вселенной — примерно 10⁸⁰, что несопоставимо меньше границы для α(n) = 4. Поэтому в инженерных прикидках DSU считают структурой с константной стоимостью операции — но помните, что формально это не константа.

И это не недоработка: Фредман и Сакс в 1989 году («The cell probe complexity of dynamic data structures», STOC) доказали нижнюю оценку Ω(α(n)) на амортизированную стоимость в модели cell-probe. Лучше — нельзя.

Сводка по вариантам (для m операций над n элементами):

Реализация Стоимость find Итого на m операций
Наивный лес O(n) худший O(m·n)
Только union by size O(log n) худший O(m log n)
Только сжатие пути O(log n) амортиз. Θ(n + m·log₁₊ₘ/ₙ n)
Обе эвристики O(α(n)) амортиз. O(m·α(n))

Реализация

Псевдокод

инициализация: для каждого i -> parent[i] = i, size[i] = 1

find(x):
    r = x
    пока parent[r] != r: r = parent[r]      # шаг 1: найти корень
    пока parent[x] != r:                    # шаг 2: сжать путь
        next = parent[x]; parent[x] = r; x = next
    вернуть r

union(a, b):
    ra = find(a); rb = find(b)
    если ra == rb: вернуть ложь             # уже вместе
    если size[ra] < size[rb]: поменять ra и rb
    parent[rb] = ra; size[ra] += size[rb]
    вернуть истину

Python: базовая версия

class DSU:
    """Система непересекающихся множеств: union by size + сжатие пути."""

    __slots__ = ("parent", "size", "components")

    def __init__(self, n: int) -> None:
        self.parent = list(range(n))   # parent[i] — родитель i; для корня parent[i] == i
        self.size = [1] * n            # size[r] осмыслен только для корня r
        self.components = n            # число текущих компонент — почти бесплатный бонус

    def find(self, x: int) -> int:
        """Итеративный поиск корня с полным сжатием пути. Амортизированно O(alpha(n))."""
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        # второй проход: переподвешиваем весь путь к корню
        while self.parent[x] != root:
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a: int, b: int) -> bool:
        """Объединяет множества. True, если слияние действительно произошло."""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:   # меньшее дерево — под большее
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

    def connected(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)

    def set_size(self, x: int) -> int:
        """Размер множества, содержащего x."""
        return self.size[self.find(x)]

Инициализация — O(n) по времени и памяти. Каждая операция — O(α(n)) амортизированно. Память — два массива по n машинных слов; в Python лучше взять array('i', ...) или numpy, если n измеряется миллионами.

Однопроходная альтернатива find — path halving; она короче и обычно быстрее:

def find_halving(self, x: int) -> int:
    """Один проход: каждый второй узел переподвешивается к деду."""
    while self.parent[x] != x:
        self.parent[x] = self.parent[self.parent[x]]   # прыжок через одного
        x = self.parent[x]
    return x

Экономия памяти: один массив вместо двух

Классический трюк: у корня в parent хранить −size (отрицательное число), у остальных — обычного родителя. Отрицательность и служит признаком корня. Память сокращается вдвое, а локальность улучшается — на больших n это заметно на кэше (см. модель памяти в https://courses.digitable.life/post/data-structures/01-complexity-and-memory/).

class CompactDSU:
    """Один массив: p[i] >= 0 — родитель, p[i] < 0 — корень с size = -p[i]."""

    def __init__(self, n: int) -> None:
        self.p = [-1] * n

    def find(self, x: int) -> int:
        while self.p[x] >= 0:
            gp = self.p[self.p[x]]
            if gp >= 0:                 # path halving
                self.p[x] = gp
            x = self.p[x]
        return x

    def union(self, a: int, b: int) -> bool:
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.p[a] > self.p[b]:       # p хранит -size: "больше" = меньше по размеру
            a, b = b, a
        self.p[a] += self.p[b]          # накапливаем размер
        self.p[b] = a
        return True

Go: ядро структуры

// DSU — union by size + сжатие пути методом path halving.
// int32 вместо int вдвое сокращает трафик к памяти при n до двух миллиардов.
type DSU struct {
	parent []int32
	size   []int32
}

// Find возвращает представителя множества, попутно укорачивая путь.
func (d *DSU) Find(x int32) int32 {
	for d.parent[x] != x {
		d.parent[x] = d.parent[d.parent[x]] // прыжок к деду
		x = d.parent[x]
	}
	return x
}

// Union объединяет множества; возвращает false, если они уже совпадали.
func (d *DSU) Union(a, b int32) bool {
	ra, rb := d.Find(a), d.Find(b)
	if ra == rb {
		return false
	}
	if d.size[ra] < d.size[rb] {
		ra, rb = rb, ra
	}
	d.parent[rb] = ra
	d.size[ra] += d.size[rb]
	return true
}

Подробнее про идиоматику языка — в треке https://courses.digitable.life/post/golang/00-overview/.

Классическое применение: алгоритм Краскала

Минимальное остовное дерево строится так: отсортировать рёбра по весу и жадно добавлять те, что соединяют пока не связанные компоненты. Проверка «не образует ли ребро цикл» — это ровно find(u) != find(v).

def kruskal(n: int, edges: list[tuple[int, int, int]]) -> tuple[int, list]:
    """edges: список (вес, u, v). Возвращает (суммарный вес, список рёбер MST)."""
    dsu = DSU(n)
    mst, total = [], 0
    for w, u, v in sorted(edges):          # O(E log E) — доминирующая часть
        if dsu.union(u, v):                # O(alpha(n)) — практически бесплатно
            mst.append((u, v, w))
            total += w
            if len(mst) == n - 1:          # ранний выход: остов собран
                break
    return total, mst

Сложность — O(E log E) на сортировку плюс O(E·α(V)) на DSU. Обратите внимание: сама структура настолько дёшева, что не влияет на асимптотику алгоритма. Если рёбра уже отсортированы или веса целые и сортируются поразрядно, Краскал становится почти линейным.

Расширения, которые встречаются в бою

DSU с весами (потенциалами)

Иногда нужно знать не только «в одном ли множестве», но и отношение между элементами: разницу величин, чётность, сдвиг. Храним для каждого узла вес ребра к родителю, а find возвращает суммарный вес до корня. Так решаются задачи вида «известно, что x минус y равно 7 — не противоречат ли ограничения друг другу».

class WeightedDSU:
    """Поддерживает ограничения вида value[b] - value[a] = w и проверку их согласованности."""

    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.size = [1] * n
        self.d = [0] * n            # d[x] = value[x] - value[parent[x]]

    def find(self, x: int) -> tuple[int, int]:
        """Возвращает (корень, value[x] - value[корня])."""
        root, acc = x, 0
        while self.parent[root] != root:
            acc += self.d[root]
            root = self.parent[root]
        cur, cur_pot = x, acc        # второй проход: сжимаем путь, пересчитывая веса
        while self.parent[cur] != root:
            nxt, nxt_d = self.parent[cur], self.d[cur]
            self.parent[cur], self.d[cur] = root, cur_pot
            cur, cur_pot = nxt, cur_pot - nxt_d
        return root, acc

    def union(self, a: int, b: int, w: int) -> bool:
        """Задаёт value[b] - value[a] = w. False, если это противоречит уже известному."""
        ra, pa = self.find(a)
        rb, pb = self.find(b)
        if ra == rb:
            return pb - pa == w      # проверка согласованности, а не объединение
        delta = w + pa - pb          # value[rb] - value[ra]
        if self.size[ra] < self.size[rb]:
            ra, rb, delta = rb, ra, -delta
        self.parent[rb], self.d[rb] = ra, delta
        self.size[ra] += self.size[rb]
        return True

    def diff(self, a: int, b: int) -> int | None:
        """value[b] - value[a], либо None, если связь неизвестна."""
        ra, pa = self.find(a)
        rb, pb = self.find(b)
        return pb - pa if ra == rb else None

Частный случай с весами по модулю 2 — «двудольный DSU»: он отвечает на вопрос, останется ли граф двудольным после добавления ребра, и находит первое ребро, создающее нечётный цикл.

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

Сжатие пути делает изменения «размазанными» и необратимыми. Если нужны откаты, от него отказываются: оставляют только union by size (строгие O(log n)) и ведут стек изменений.

class RollbackDSU:
    """Union by size без сжатия пути: find за O(log n), зато операции обратимы."""

    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.size = [1] * n
        self.history: list[tuple[int, int]] = []   # (подвешенный корень, корень-приёмник)

    def find(self, x: int) -> int:
        while self.parent[x] != x:                  # никакого сжатия!
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.history.append((rb, ra))
        return True

    def snapshot(self) -> int:
        return len(self.history)

    def rollback(self, to: int) -> None:
        """Откатывает все объединения, сделанные после снимка to."""
        while len(self.history) > to:
            rb, ra = self.history.pop()
            self.size[ra] -= self.size[rb]
            self.parent[rb] = rb

Зачем это нужно: оффлайн-динамическая связность. Если заранее известен весь поток запросов, каждое ребро «живёт» на отрезке времени. Строим дерево отрезков по оси времени, кладём каждое ребро в O(log Q) его узлов и обходим дерево в глубину, объединяя на входе в узел и откатывая на выходе. Получаем O(Q log Q log V) на задачу, где рёбра и добавляются, и удаляются. Про дерево отрезков — в следующей статье трека, https://courses.digitable.life/post/data-structures/12-segment-and-fenwick-trees/.

Хранение содержимого множеств: small-to-large

Базовый DSU не умеет перечислять элементы множества. Если это нужно, храните у корня контейнер (список, set, хеш-таблицу — см. https://courses.digitable.life/post/data-structures/05-hash-tables/) и при слиянии всегда переливайте содержимое меньшего в больший. Каждый элемент переезжает не более log n раз, поэтому суммарная стоимость всех слияний — O(n log n). Тот же приём («small to large», или merging by weight) — основа быстрых решений задач на поддеревьях.

Другие направления

  • Персистентный DSU. Если parent хранить в персистентном массиве на основе неизменяемого дерева, можно обращаться к любой прошлой версии структуры. Цена — O(log n) на доступ и рост потребления памяти. См. https://courses.digitable.life/post/data-structures/14-persistent-and-concurrent/.
  • Конкурентный DSU. Существуют lock-free реализации на CAS: union конкурирует за запись в корень, find может «помогать» сжатием. Современный анализ — Jayanti и Tarjan, «Concurrent Disjoint Set Union» (arXiv:2003.01203). Приятная особенность: сжатие пути идемпотентно, поэтому гонка на нём не ломает корректность.

Где это применяют на практике

Компиляторы. В алгоритме Хиндли–Милнера типовые переменные объединяются в классы эквивалентности процедурой унификации — это буквально union-find; ошибка «cannot unify» есть неудачная попытка union. В LLVM для этого существует готовый шаблон llvm::EquivalenceClasses, применяемый в анализах алиасинга и слиянии значений. Про статическую типизацию в целом — https://courses.digitable.life/post/typescript/00-overview/.

Компьютерное зрение и физика. Двупроходная разметка связных компонент бинарного изображения: на первом проходе присваиваем временные метки и объединяем эквивалентные через DSU, на втором заменяем метки на представителей. В физике перколяции тот же алгоритм известен как алгоритм Хошена–Копельмана. Сегментация изображений Фельценсцвальба и Хаттенлохера — это, по сути, Краскал с адаптивным порогом слияния.

Обработка данных. В задачах дедупликации (одинаковые пользователи, товары, организации из разных источников) DSU превращает попарные признаки «эти две записи — вероятно, одно и то же» в кластеры сущностей. При миллиардах записей это делают распределённо — итеративным алгоритмом hash-to-min или label propagation, потому что классический DSU плохо шардируется: он существенно последовательный. Из готовых библиотек стоит знать boost::disjoint_sets в C++ и scipy.sparse.csgraph.connected_components в Python; в стандартной библиотеке Java такого класса нет, и его пишут вручную.

Типичные ошибки

  1. Сравнение parent[a] == parent[b] вместо find(a) == find(b). Родитель — не представитель. Работает на маленьких тестах, ломается на больших. Самая частая ошибка.
  2. Рекурсивный find. Красив, но на цепочке из 10⁶ элементов даёт переполнение стека (в Python — RecursionError уже около 1000). Пишите итеративно; это ещё и быстрее.
  3. Ранг трактуется как высота. После сжатия пути rank перестаёт быть настоящей высотой и остаётся лишь верхней оценкой. Никогда не используйте его как «глубину дерева» в логике задачи.
  4. size читается у не-корня. Массив size осмыслен только для корней. Всегда size[find(x)].
  5. Сжатие пути вместе с откатами. Комбинация некорректна: сжатие меняет структуру недетерминированно и не пишется в журнал. В RollbackDSU сжатия быть не должно.
  6. Ожидание удаления рёбер. DSU принципиально монотонен: множества только сливаются. Задача с удалением решается либо оффлайн (дерево отрезков по времени + откаты), либо совсем другой структурой.
  7. Игнорирование возвращаемого значения union. bool из union — бесплатный ответ на вопросы «было ли ребро лишним», «образовался ли цикл», «сколько компонент осталось». Не выбрасывайте его.
  8. Смещение индексов и гонки. При нумерации вершин с 1 заводите массив на n + 1 элемент. И помните: обычный DSU не потокобезопасен — одновременные union теряют записи, нужна либо общая блокировка, либо lock-free реализация.
  9. DSU там, где нужна другая структура. Если требуются пути, расстояния или порядок внутри компоненты, DSU не поможет — он знает только «кто с кем в одной группе». Смотрите деревья (https://courses.digitable.life/post/data-structures/06-trees-bst/) и представления графов (https://courses.digitable.life/post/data-structures/10-graphs-representation/).

Когда выбирать DSU

Ситуация Решение
Рёбра только добавляются, нужна связность, размеры компонент, MST Обычный DSU — идеальный вариант
Нужны отношения (разницы, чётность) внутри компоненты Взвешенный DSU
Рёбра удаляются, но все запросы известны заранее DSU с откатом + дерево отрезков по времени
Рёбра удаляются в онлайне Не DSU: link-cut и HDT-структуры
Нужен кратчайший путь или сам путь между вершинами Не DSU: BFS, Dijkstra, обход графа
Нужно перечислять элементы множества DSU + надстройка small-to-large

Мини-итог

  • DSU — это лес деревьев, где корень служит представителем множества; форма деревьев не несёт смысла и потому свободно оптимизируется.
  • Две эвристики — объединение по размеру и сжатие пути — превращают O(n) в O(α(n)), что неотличимо от константы, и эта граница доказано оптимальна.
  • Память — один-два целочисленных массива, никаких указателей и аллокаций: отличная работа с кэшем.
  • Структура монотонна: слияния бывают, разделений — нет; всё, что связано с удалением, решается оффлайн-приёмами или другими структурами. Практические варианты — с весами, с откатом, small-to-large, персистентный и конкурентный.

Источники

  • Thomas H. Cormen et al. Introduction to Algorithms, 4th ed., глава 19 «Data Structures for Disjoint Sets» — mitpress.mit.edu
  • Robert Sedgewick, Kevin Wayne. Algorithms, 4th ed., раздел 1.5 «Case Study: Union-Find» — algs4.cs.princeton.edu/15uf
  • Robert E. Tarjan. Efficiency of a Good But Not Linear Set Union Algorithm, JACM 1975 — dl.acm.org
  • Robert E. Tarjan, Jan van Leeuwen. Worst-case Analysis of Set Union Algorithms, JACM 1984 — dl.acm.org
  • Michael Fredman, Michael Saks. The cell probe complexity of dynamic data structures, STOC 1989 — dl.acm.org
  • Siddhartha Jayanti, Robert Tarjan. Concurrent Disjoint Set Union, 2020 — arxiv.org/abs/2003.01203
  • cp-algorithms: Disjoint Set Union — практические варианты и задачи: cp-algorithms.com
  • Boost.DisjointSets — эталонная промышленная реализация на C++: boost.org

Что дальше

Мы разобрали структуру, которая отвечает на вопросы о принадлежности к группе. Следующий шаг — структуры, отвечающие на вопросы об агрегатах на отрезках: сумма, минимум, максимум на диапазоне с одновременной поддержкой обновлений. Они же дают ключ к оффлайн-динамической связности, о которой шла речь выше.

Читайте дальше: Дерево отрезков и дерево Фенвика. Вернуться к общей картине — карта трека «Структуры данных».

Нашли неточность? Выделите фрагмент текста — рядом появится жучок.

Нужен разбор именно вашей ситуации?

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

Доска запросов