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

Как за почти-константу узнавать, в одной ли «компании» два элемента, и сливать компании. Основа Краскала и многих задач на связность.

DSU (Disjoint Set Union, Union-Find) — структура, которая поддерживает разбиение элементов на непересекающиеся множества и быстро отвечает на запросы «в одном ли множестве два элемента?» и «объедини их множества».

Зачем это нужно

Представь, что есть люди и связи дружбы, которые добавляются по одной. Нужно отвечать: «дружат ли (напрямую или через цепочку) a и b?». DSU делает это почти за константу. Эта структура — рабочая лошадка олимпиад: на ней строится алгоритм Краскала для минимального остова, она считает компоненты связности, решает задачи об объединении регионов, обрабатывает запросы связности офлайн. Простая в реализации (десяток строк) и невероятно эффективная — обязательна к освоению.

Идея «на пальцах»

Каждое множество представляем деревом, у которого есть «представитель» — корень. Массив parent[x] хранит родителя элемента x; у корня родитель — он сам. Две операции:

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

Два элемента в одном множестве ⇔ у них общий корень. Без оптимизаций дерево может выродиться в цепочку, и find станет O(n). Поэтому добавляют две хитрости.

Две оптимизации, которые делают DSU быстрым

• Сжатие путей (path compression): при find подвешиваем встреченные вершины напрямую к корню — дерево становится плоским.
• Объединение по размеру/рангу: при union подвешиваем меньшее дерево под большее, чтобы не растить высоту.

Вместе они дают почти константную амортизированную сложность O(α(n)), где α — обратная функция Аккермана, которая для любых реальных n не превышает 4–5. На практике — считай, что это O(1).

Реализация

class DSU:
    def __init__(self, n):
        self.p = list(range(n))     # сначала каждый сам себе корень
        self.size = [1] * n         # размер дерева у корня

    def find(self, x):
        # подъём к корню со сжатием пути
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]   # подвешиваем к деду
            x = self.p[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False            # уже в одном множестве
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra         # ra — больший корень
        self.p[rb] = ra             # меньшее дерево под большее
        self.size[ra] += self.size[rb]
        return True

dsu = DSU(6)
for a, b in [(0, 1), (1, 2), (3, 4)]:
    dsu.union(a, b)
print("0 и 2 связаны:", dsu.find(0) == dsu.find(2))
print("0 и 3 связаны:", dsu.find(0) == dsu.find(3))
comps = len({dsu.find(i) for i in range(6)})
print("Число компонент:", comps)

Разберём результат: мы объединили {0,1,2} и {3,4}, а вершина 5 осталась одна. Значит, 0 и 2 связаны, 0 и 3 — нет, а всего получилось 3 компоненты: {0,1,2}, {3,4}, {5}. Число различных корней = число компонент.

Вывод:

0 и 2 связаны: True
0 и 3 связаны: False
Число компонент: 3

Применения DSU

Сложность

С обеими оптимизациями: find и union — амортизированно O(α(n)) ≈ O(1). Память — O(n) (массивы родителей и размеров). Это делает DSU идеальным для задач с большим числом операций объединения и проверки.

Подводные камни

• Не забывай обе оптимизации. Без сжатия путей и объединения по размеру дерево вырождается, и find становится O(n).
• DSU не умеет «разъединять». Структура поддерживает только объединение; удаление связей требует других техник (например, офлайн-обработки или persistent-структур).
• Сравнивай корни, а не сами элементы: «в одном множестве» — это find(a) == find(b), а не a == b.

Итог

• DSU поддерживает разбиение на множества с операциями find (корень) и union (слияние).
• Сжатие путей + объединение по размеру дают почти константную сложность O(α(n)).
• Два элемента в одном множестве ⇔ у них общий корень; число корней = число компонент.
• Основа Краскала, подсчёта компонент и задач на динамическую связность; «разъединять» DSU не умеет.