Підтримка множин (Union‑Find / DSU)

Повне пояснення

Коротке пояснення

Union‑Find (DSU) зберігає елементи у вигляді дерев, де кожен вузол вказує на батька. Операція find повертає корінь дерева, а union об’єднує два дерева, вибираючи менш високий як підлеглий.

Аналогія

Уявіть, що кожен елемент — це учень, а корінь дерева — його керівник. Якщо двоє учнів працюють разом, їхні керівники об’єднуються в одного.

Коли застосовувати

• Потрібно швидко перевіряти, чи два елементи належать одній групі.
• Задача включає багато операцій union і find, наприклад, у графах.
• Необхідна ефективність: O(α(n)) на операцію.
• Коли потрібен розподіл елементів у компоненти зв’язності.

Кроки алгоритму

1. Ініціалізувати масив parent, де кожен елемент сам себе батьком.
2. Ініціалізувати масив rank (висота дерева) нулями.
3. Для find: рекурсивно переходити до батька, застосовуючи path compression.
4. Для union: знайти корені обох елементів, порівняти rank і приєднати менший до більшого.
5. Якщо ranks однакові, збільшити rank нового кореня на 1.

Візуальна інтуїція (текстова)

  a   b
  |   |
  c---d   // після union(a,d)

Складність

Час: амортизована O(α(n)) (почти константна). Пам’ять: O(n) для масивів parent і rank.

Код (js)

// Union‑Find з path compression і union by rank
class UnionFind {
  constructor(size) {
    // parent[i] – батько елемента i
    this.parent = Array.from({ length: size }, (_, i) => i);
    // rank[i] – оцінка висоти дерева, використовується для балансування
    this.rank = Array(size).fill(0);
  }

  // Знаходження кореня елемента з path compression
  find(x) {
    if (this.parent[x] !== x) {
      // рекурсивно шукаємо корінь і «сплющуємо» шлях
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  // Об’єднуємо два елементи, використовуючи rank
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return; // вже в одній групі

    // Приєднуємо дерево з меншим 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 {
      // Якщо ranks однакові, підвищуємо rank нового кореня
      this.parent[rootY] = rootX;
      this.rank[rootX] += 1;
    }
  }
}

// Тестовий приклад
const uf = new UnionFind(5);
uf.union(0, 1); // об’єднуємо 0 і 1
uf.union(3, 4); // об’єднуємо 3 і 4
console.log(uf.find(0) === uf.find(1)); // очікуваний результат: true
console.log(uf.find(0) === uf.find(3)); // очікуваний результат: false

Типові помилки і поради

1. Не використовувати path compression – це знижує складність до O(log n). Додайте рекурсивне присвоєння parent[x] = find(parent[x]).
2. Забути про rank – без балансування дерева може стати лінійним, що погіршить час O(n). Додавайте rank і порівнюйте його.
3. Використовувати == замість === – це може призвести до неправильних порівнянь типу.
4. Не ініціалізувати масиви правильно – використовуйте Array.from або заповнювання, щоб уникнути спільних посилань.
5. Забувати про 0‑індексацію – у JS індекси починаються з нуля, тому перевіряйте розміри.

Перевір себе

1. Що робить операція find у Union‑Find?
2. Яка роль масиву rank при об’єднанні двох елементів?