Disjoint Set (Union-Find)

Disjoint Set (Union-Find) — структура данных для эффективного объединения элементов в группы и проверки принадлежности двух элементов одной группе.

Зачем нужно

Некоторые задачи требуют динамически объединять элементы и быстро проверять связность. Например: принадлежат ли два города одной железнодорожной сети? Naïve подход с обходом графа — O(n) на каждый запрос. Union-Find даёт почти O(1) благодаря двум оптимизациям: union by rank и path compression.

Где используется

  • Алгоритм Крускала (минимальное остовное дерево)
  • Определение циклов в графе
  • Задачи связности: сети, компоненты связности
  • Онлайн-алгоритмы с динамическим добавлением рёбер

Основной контент

Идея

Каждый элемент принадлежит множеству, представленному «лидером» (root). Два элемента в одном множестве имеют одного root.

Начало: {0} {1} {2} {3} {4}
После union(0,1): {0,1} {2} {3} {4}
После union(2,3): {0,1} {2,3} {4}
После union(0,2): {0,1,2,3} {4}

find(1) == find(3)?  → да, оба в {0,1,2,3}
find(1) == find(4)?  → нет

Реализация

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }

  // Найти root (с path compression)
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // сжатие пути
    }
    return this.parent[x];
  }

  // Объединить два множества (union by rank)
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return false; // уже в одном множестве

    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]++;
    }
    return true;
  }

  // Проверить: в одном ли множестве?
  connected(x, y) {
    return this.find(x) === this.find(y);
  }
}

// Использование
const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(2, 3);
uf.union(0, 2);

console.log(uf.connected(1, 3)); // true
console.log(uf.connected(1, 4)); // false

Сложность

Операция Без оптимизаций С оптимизациями
find O(n) O(α(n)) ≈ O(1)
union O(n) O(α(n)) ≈ O(1)

α(n) — обратная функция Аккермана, практически константа для любых реальных n.

Частые ошибки

  • Нет path compression — find без сжатия пути превращается в O(n) при цепочечных union
  • Путаница find и union — find возвращает root, не элемент; сравнивай результаты find: find(x) === find(y)
  • Проверка после union — union возвращает false, если элементы уже в одном множестве; используй это для обнаружения циклов в графе

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

Ресурсы