Union-Find (система непересекающихся множеств)

Начни с простейшей корректной реализации: массив `parent`, где `parent[i]` — представитель элемента i, или сам i, если i является корнем. `find(x)` поднимается по указателям родителей до корня — в худшем случае это O(n) шагов, когда структура вырождается в цепочку (union всегда дописывает в хвост). `union(a, b)` вызывает find для обоих, затем указывает один корень на другой. `connected(a, b)` возвращает, равны ли find(a) и find(b). `count()` отслеживает число непересекающихся множеств. Сначала построй и протестируй эту версию: отточи все инварианты до того, как оптимизации скроют логику. Два элемента в одной компоненте тогда и только тогда, когда их значения find равны — это единственная аксиома, которую ты сохранишь во всех последующих изменениях.

Наивный union всегда произвольно прикрепляет один корень под другой, поэтому n-1 объединений могут построить цепочку глубиной n-1, превращая каждый find в обход O(n). Объединение по рангу предотвращает это: каждый узел несёт `rank` (верхнюю оценку высоты своего поддерева), изначально 0. При слиянии двух деревьев помещай корень меньшего ранга под корень большего, так что комбинированное дерево не глубже наиболее глубокого из двух. При равных рангах повышай один (например, b под a) и увеличивай ранг a на единицу. Это гарантирует, что дерево ранга k содержит минимум 2^k узлов, поэтому максимальная глубина любого дерева на n элементах — O(log n) — find теперь O(log n) в худшем случае, а не O(n). Держи массив рангов рядом с parent; ранги никогда не убывают и не меняются после того, как узел перестаёт быть корнем.

Объединение по рангу ограничивает высоту дерева O(log n), но можно лучше: каждый раз, когда find(x) проходит цепочку до корня r, переназначи parent каждого узла на этом пути прямо на r. Это сжатие пути (или «полное сжатие пути» / «path halving» — оба варианта допустимы). Следующий вызов find для любого из этих узлов — O(1), потому что они теперь указывают прямо на корень. Сжатие пути не меняет ранги — они остаются статичными верхними оценками, высота дерева не пересчитывается. Совместный эффект union-by-rank и сжатия пути даёт амортизированную стоимость операции O(α(n)), где α — обратная функция Аккермана — для всех практических значений n (до 2^65536) α(n) ≤ 5. Это так близко к константе, как это возможно для известных структур данных с той же выразительностью.

Убедившись, что обе оптимизации работают, проверь публичный контракт на adversarial входах. `connected(a, b)` — это просто `find(a) === find(b)` — никогда не реализуй его ручным обходом дерева. `count()` должен уменьшаться ровно на 1 при каждом объединении двух ранее несвязанных элементов и оставаться неизменным, если они уже были связаны. Напиши стресс-тест: начни с n=1000 элементов, применяй случайные объединения и после каждого пакета проверяй, что count равен n минус количество успешных объединений (тех, что реально слили два разных множества). Это инвариант, который ловит ошибки off-by-one в условии защиты union. Также явно проверь транзитивность: после union(0,1) и union(1,2) connected(0,2) должно быть истинным, даже если 0 и 2 никогда не объединялись напрямую.

Граница обратной функции Аккермана — не просто теоретический курьёз — докажи это эмпирически. Запусти бенчмарк: для n из [1000, 10 000, 100 000, 1 000 000] выполни n случайных объединений, затем n случайных find, и измерь общее время. Если реализация корректна, время должно расти почти линейно с n (а не n log n у версии только с рангом). Критическая проверка — что сжатие пути реально срабатывает: после пакета find на структуре, построенной adversarial последовательными объединениями, убедись, что средняя длина цепочки parent сократилась до почти 1. Это упражнение также раскрывает разницу между worst-case и амортизированным анализом: один find на свежей цепочке всё ещё может быть O(log n), но амортизированно по последовательности из m операций на n элементах итого O(m α(n)) — амортизация по последовательности, а не по одному вызову.

Примени DSU к реальной задаче. Алгоритм Краскала находит минимальное остовное дерево взвешенного неориентированного графа за O(E log E): отсортируй все рёбра по весу, затем итерируй; для каждого ребра (u, v, w), если u и v в разных компонентах (не связаны), добавь ребро в MST и выполни union(u, v). Останови, когда count() равен 1 (все узлы связаны) или все рёбра исчерпаны. DSU — единственная причина эффективности Краскала — проверка связности и слияние оба почти O(1). Как альтернатива (или дополнение), реализуй симуляцию перколяции: на сетке n×n открывай ячейки по одной в случайном порядке и используй DSU для обнаружения первого момента, когда верхний и нижний ряды становятся связанными — это порог перколяции, классическая демонстрация того, что DSU превращает иначе O(n^4) симуляцию в O(n^2 α(n^2)).