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

Union-Find (DSU) хранит разбиение элементов на множества как лес: `find(x)` возвращает корень-представителя, `union(a, b)` подвешивает один корень к другому. С двумя эвристиками операции работают за амортизированное `O(α(n))` — практически константу.

Эвристики

• Сжатие пути: при find перенаправлять узлы ближе к корню.
• Объединение по размеру (рангу): меньшее дерево подвешивать к большему.
• Без эвристик дерево вырождается в цепочку — O(n) на операцию; с одной из них — O(log n); с обеими — O(α(n)), где обратная функция Аккермана α(n) ≤ 4 для любых реальных n.

class DSU {
  #parent; #size;
  constructor(n) {
    this.#parent = Array.from({ length: n }, (_, i) => i);
    this.#size = new Array(n).fill(1);
  }
  find(x) {
    // halving: подвешиваем x к «деду» и прыгаем туда
    while (this.#parent[x] !== x) x = this.#parent[x] = this.#parent[this.#parent[x]];
    return x;
  }
  union(a, b) {
    [a, b] = [this.find(a), this.find(b)];
    if (a === b) return false;
    if (this.#size[a] < this.#size[b]) [a, b] = [b, a];
    this.#parent[b] = a;
    this.#size[a] += this.#size[b];
    return true;
  }
}

Где применяется

• Алгоритм Краскала.
• Цикл в неориентированном графе: union вернул false — концы ребра уже связаны.
• Компоненты связности при добавлении рёбер, слияние аккаунтов по общим email.

Коротко для собеседования

DSU почти за константу отвечает, связаны ли уже два элемента, если одновременно сжимать пути и подвешивать меньшее дерево к большему. Применяйте его в Краскале и для поиска циклов при добавлении рёбер; удаление рёбер он не поддерживает — только офлайн-приёмы.