Union-Find (DSU)

Union-Find (Disjoint Set Union, DSU) — это структура данных для работы с классами эквивалентности или динамической связностью. Она поддерживает две операции: find(x) — найти представителя (корень) группы, к которой принадлежит элемент x, и union(x, y) — объединить группы элементов x и y. Магия DSU в том, что с двумя простыми оптимизациями обе операции выполняются за почти O(1) — точнее, за O(α(n)), где α — обратная функция Аккермана, которая растёт настолько медленно, что для всех практических значений n (даже n = 10¹⁸) α(n) ≤ 4.

Основная идея: представляем каждую группу как дерево, где корень — это представитель группы. Массив parent[i] хранит родителя узла i. Если parent[i] = i, то i — корень (представитель своей группы). Операция find(x) поднимается по дереву от x к корню: while (parent[x] != x) { x = parent[x]; }. Операция union(x, y) находит корни обоих элементов и присоединяет одно дерево к другому: parent[root_y] = root_x.

Когда применять / Мотивация

Идея / Как работает

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

Оптимизация 1: Union by Rank (или Union by Size). При объединении двух деревьев присоединяем меньшее дерево к большему (по рангу или размеру). Ранг — это оценка высоты дерева. При слиянии деревьев одинакового ранга ранг нового корня увеличивается на 1. Это гарантирует, что высота дерева не превышает log₂(n), и find выполняется за O(log n).

Оптимизация 2: Path Compression. При выполнении find(x) мы поднимаемся от x к корню. Зачем сохранять длинный путь? После того как нашли корень, можем перевесить все узлы на пути прямо на корень: parent[x] = root. Это «сжимает» путь и ускоряет все последующие операции. Реализуется одной строкой: parent[x] = find(parent[x]) — рекурсивный вызов находит корень, а присваивание сжимает путь на обратном ходе рекурсии.

Вместе union by rank и path compression дают амортизированную сложность O(α(n)) на операцию, где α — обратная функция Аккермана. Это настолько близко к O(1), что на практике разница незаметна. Удивительный математический результат (доказал Tarjan) — даже при миллиардах операций суммарная стоимость остаётся линейной.

Операция	Без оптимизаций	Union by rank	+ Path compression
find(x)	O(n)	O(log n)	O(α(n)) ≈ O(1)
union(x, y)	O(n)	O(log n)	O(α(n)) ≈ O(1)

Реализация

Задача: Number of Provinces

Дана матрица isConnected размера n×n, где isConnected[i][j] = 1 означает, что города i и j напрямую соединены дорогой. Связность транзитивна: если город A связан с B, а B связан с C, то A и C находятся в одной провинции, даже если между ними нет прямой дороги. Найти количество провинций (связных компонент).

Подход и идея решения

Это классическая задача на Union-Find. Идея: для каждого ребра (прямой связи между городами) выполняем union(i, j), объединяя города в одну группу. В конце число провинций = число различных корней (представителей групп).

Шаг 1: инициализируем DSU для n городов. Каждый город изначально — своя провинция: parent[i] = i, rank[i] = 0.

Шаг 2: проходим матрицу isConnected. Для каждой связи isConnected[i][j] = 1 (где i < j, чтобы не обрабатывать дважды) выполняем union(i, j). Если города уже в одной группе (find(i) == find(j)), union ничего не делает. Если в разных — объединяем и уменьшаем счётчик компонент.

Шаг 3: возвращаем число компонент. Можно либо сразу поддерживать счётчик (уменьшаем при успешном union), либо в конце пройти все города и подсчитать, у скольких parent[i] = i (это корни).

class UnionFind {
    constructor(n) {
      this.parent = Array.from({ length: n }, (_, i) => i);
      this.rank = new Array(n).fill(0);
      this.components = n; // число компонент
    }

    find(x) {
      // Path compression: перевешиваем узлы прямо на корень
      if (this.parent[x] !== x) {
        this.parent[x] = this.find(this.parent[x]);
      }
      return this.parent[x];
    }

    union(x, y) {
      const rootX = this.find(x);
      const rootY = this.find(y);

      // Уже в одной группе
      if (rootX === rootY) return false;

      // Union by rank: присоединяем меньшее дерево к большему
      if (this.rank[rootX] < this.rank[rootY]) {
        this.parent[rootX] = rootY;
      } else if (this.rank[rootX] > this.rank[rootY]) {
        this.parent[rootY] = rootX;
      } else {
        // Ранги равны: присоединяем к любому, увеличиваем ранг
        this.parent[rootY] = rootX;
        this.rank[rootX]++;
      }

      this.components--;
      return true;
    }

    getComponents() {
      return this.components;
    }
  }

  function findCircleNum(isConnected) {
    const n = isConnected.length;
    const uf = new UnionFind(n);

    // Обрабатываем верхний треугольник матрицы (i < j)
    for (let i = 0; i < n; i++) {
      for (let j = i + 1; j < n; j++) {
        if (isConnected[i][j] === 1) {
          uf.union(i, j);
        }
      }
    }

    return uf.getComponents();
  }

Трассировка

Трассировка: isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Интерпретация: город 0 связан с 1, город 2 изолирован.

Инициализация: parent=[0,1,2], rank=[0,0,0], components=3
i=0, j=1: isConnected[0][1]=1 → union(0,1) - find(0)=0, find(1)=1, rootX≠rootY - rank[0]=rank[1]=0 → parent[1]=0, rank[0]++ - parent=[0,0,2], rank=[1,0,0], components=2
i=0, j=2: isConnected[0][2]=0 → skip
i=1, j=2: isConnected[1][2]=0 → skip

Результат: 2 провинции ✓ ({0,1} и {2})

Path compression в действии: если позже вызвать find(1):

find(1): parent[1]=0, parent[0]=0 → возвращаем 0
На обратном ходе рекурсии: parent[1] остаётся 0 (уже сжат)

Если бы была цепь 1→2→3→корень, после find(1) получим 1→корень, 2→корень, 3→корень (все прямо на корень).

Сложность

Анализ сложности:

Time: O(n² · α(n)) ≈ O(n²) - Два вложенных цикла по матрице: O(n²) итераций - Каждая операция union/find: O(α(n)) ≈ O(1)
Space: O(n) - Массивы parent и rank: O(n) - Стек рекурсии find с path compression: O(α(n)) ≈ O(1)

Почему O(n² · α(n)), а не O(n³)? Потому что операция union/find не O(n), а O(α(n)) благодаря оптимизациям. В отличие от DFS-решения (O(n²) для обхода матрицы + O(n²) для DFS = O(n²)), DSU также O(n²), но проще в коде и легко адаптируется к динамическим запросам.

DSU применяется в задачах, где нужно динамически отслеживать группы эквивалентности: алгоритм Kruskal для поиска минимального остовного дерева (проверка циклов), задачи на связность компонент графа, объединение аккаунтов, поиск циклов в неориентированном графе, оффлайн-обработка запросов «когда A и B стали связными». Сигнальные слова в задачах: «группы», «компоненты», «объединить множества», «эквивалентность», «друзья друзей».

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

Изолированные вершины: Если у города нет связей, он сам по себе — провинция. DSU корректно обрабатывает это (components не уменьшается при отсутствии union).
Self-loops: isConnected[i][i] = 1 всегда true по определению. Не обрабатываем (пропускаем i=j в циклах).
Симметричная матрица: isConnected[i][j] = isConnected[j][i] для неориентированного графа. Обрабатываем только верхний треугольник (i < j), чтобы не вызывать union дважды.
Union by size vs rank: Union by size (присоединяем дерево с меньшим числом узлов) даёт ту же асимптотику, что и union by rank, и проще в понимании. На практике разница минимальна. Rank — более теоретически элегантное решение.
Path compression без рекурсии: Можно реализовать итеративно с двумя проходами: первый поднимается к корню, второй сжимает путь. Но рекурсивная версия короче и быстрее благодаря хвостовой оптимизации (tail recursion).
Интервьюер спросит: «Можно ли использовать DFS?» — Да, но DSU элегантнее для задач, где добавляются рёбра динамически или нужны оффлайн-запросы «когда A и B стали связными». «Что если нужно удалить ребро?» — DSU не поддерживает удаление. Нужна более сложная структура (Link-Cut Tree) или оффлайн-обработка запросов в обратном порядке.

Follow-up вопросы интервьюера

Kruskal MST (Minimum Spanning Tree): Как найти минимальное остовное дерево? — Сортируем рёбра по весу, добавляем ребро в дерево, если оно не создаёт цикл (find(u) != find(v)). DSU проверяет циклы за O(α(n)). Итого O(E log E) на сортировку + O(E·α(V)).
Redundant Connection: Найти ребро, удаление которого превратит граф в дерево. — Добавляем рёбра по одному через union. Первое ребро, где find(u) == find(v) (создаёт цикл), — искомое.
Accounts Merge: Объединить аккаунты по общим email’ам. — DSU на индексах аккаунтов. Для каждого email создаём map email → первый индекс. При встрече email во втором аккаунте — union’им индексы.
Number of Islands II (динамические запросы): Изначально пустая матрица, добавляются острова (1) по одному, нужно отвечать на число островов после каждого добавления. — DSU с динамическими union’ами. При добавлении клетки проверяем 4 соседей, union’им с существующими островами.
DSU с откатом (Rollback DSU): Как реализовать отмену операций? — Храним стек изменений (кто кому присоединялся). При rollback восстанавливаем parent и rank. НЕ используем path compression (он необратим), только union by rank. Применяется в оффлайн-алгоритмах dynamic connectivity.
Persistent DSU: Версионированная структура, где можно запросить состояние DSU на любом шаге. — Persistent array для parent/rank (каждое изменение создаёт новую версию). Сложно, редко встречается на интервью.

Чеклист на собес

Реализовал две оптимизации: union by rank (или size) и path compression — без них O(n).
Помню, что амортизированная сложность операций — O(α(n)), это «почти O(1)» на любых разумных n.
В union возвращаю boolean: успешное слияние vs «уже в одной группе» — это удобно для cycle detection.
Поддерживаю счётчик компонент внутри DSU, чтобы не пересчитывать в конце.
Узнаю DSU по сигнальным словам: «группы», «связные компоненты», «объединить», «друзья друзей», «провинции», «islands II».
Готов обсудить trade-off с DFS: DSU выигрывает для динамических и оффлайн запросов.
Помню ограничения: DSU не поддерживает удаление рёбер. Для этого — Link-Cut Tree или offline reverse.