Skip to content

🔗 Система от Нейерархични Множества (Disjoint Set Union - DSU)

Системата от нейерархични множества (известна още като Union-Find) е структура от данни, която поддържа разделяне на множество от елементи на няколко несиметрични (нейерархични) подмножества. Тази структура е от съществено значение за ефективното решаване на множество проблеми, свързани с графи, мрежи и динамична свързаност.

DSU е особено полезна, когато трябва да поддържаме колекция от елементи, разделени на непресичащи се групи, и да отговаряме бързо на заявки от типа "Принадлежат ли два елемента на една и съща група?" или "Обедини групите на два елемента".

1. Основни Операции

DSU поддържа две основни операции:

  1. Find(i): Определя в кое подмножество се намира елементът \(i\). Обикновено връща "представител" (корен) на това подмножество. Ако find(i) == find(j), то \(i\) и \(j\) са в едно и също множество. Тази операция е основата за проверка на принадлежност към множество.

  2. Union(i, j): Обединява подмножествата, в които се намират \(i\) и \(j\). След тази операция, всички елементи от двете множества ще имат общ представител.

Допълнителни операции, които често се използват: - MakeSet(i): Създава ново множество с един елемент \(i\). - GetSize(i): Връща размера на множеството, съдържащо елемент \(i\). - CountSets(): Връща общия брой на отделните множества.

2. Имплементация и Оптимизации

Наивната имплементация може да доведе до вериги с дължина \(O(N)\). За да постигнем почти константно време, използваме две важни оптимизации. Без тези оптимизации, в най-лошия случай можем да получим дълбоко дърво, което прави операцията find линейна по време.

2.1. Свиване на пътищата (Path Compression)

При всяко извикване на find(i), правим всички възли по пътя към корена директни деца на корена. Тази техника е изключително ефективна - когато търсим корена на даден елемент, всички елементи по пътя се "свиват" и започват да сочат директно към корена.

Как работи: Когато търсим find(i) и минаваме през верига от родители i → p1 → p2 → ... → root, след завършване на операцията всички тези междинни възли p1, p2, ... вече сочат директно към root.

Тази оптимизация прави следващите заявки за същите елементи много по-бързи, тъй като пътят до корена става практически директен.

2.2. Обединяване по ранг/размер (Union by Rank/Size)

Винаги закачаме "по-плиткото" дърво към корена на "по-дълбокото", за да запазим височината минимална. Има два варианта:

  • Union by Size: Закачаме по-малкото множество към по-голямото.
  • Union by Rank: Закачаме дървото с по-малка височина към дървото с по-голяма височина.

И двете дават отлични резултати, като на практика union by size е по-популярен, защото размерът на множествата често е полезна информация сам по себе си.

struct DSU {
    vector<int> parent;  // parent[i] пази родителя на елемент i
    vector<int> sz;      // sz[i] пази размера на множеството с корен i

    // Конструктор - инициализация
    DSU(int n) {
        parent.resize(n + 1);
        sz.resize(n + 1, 1);
        // Всеки елемент е в свое собствено множество
        for (int i = 1; i <= n; i++) parent[i] = i;
    }

    // Find с path compression
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]); // Path compression
    }

    // Union по размер
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            // Винаги закачаме по-малкото към по-голямото
            if (sz[root_i] < sz[root_j]) swap(root_i, root_j);
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
        }
    }

    // Проверка дали два елемента са в едно множество
    bool same(int i, int j) {
        return find(i) == find(j);
    }

    // Получаване на размера на множеството
    int getSize(int i) {
        return sz[find(i)];
    }
};

Сложност: С двете оптимизации, операциите са почти \(O(1)\) (технически \(O(\alpha(N))\), където \(\alpha\) е обратната функция на Акерман). На практика \(\alpha(N) \leq 4\) за всички реални стойности на \(N\), което прави операциите ефективно константни.

2.3. Вариант с ранг

Ако предпочитате union by rank вместо union by size:

struct DSU_Rank {
    vector<int> parent;
    vector<int> rank;  // rank[i] е приблизителната височина на дървото

    DSU_Rank(int n) {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        for (int i = 1; i <= n; i++) parent[i] = i;
    }

    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            if (rank[root_i] < rank[root_j]) {
                parent[root_i] = root_j;
            } else if (rank[root_i] > rank[root_j]) {
                parent[root_j] = root_i;
            } else {
                parent[root_j] = root_i;
                rank[root_i]++;  // Увеличаваме ранга само при равенство
            }
        }
    }
};

3. Приложения

DSU е невероятно универсална структура с многобройни приложения в различни области.

3.1. Алгоритъм на Крускал (Minimum Spanning Tree)

Алгоритъмът на Крускал намира минимално покриващо дърво в претеглен граф. DSU е централна част от този алгоритъм:

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

long long kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end()); // Сортираме по тегло
    DSU dsu(n);
    long long total_weight = 0;
    int edges_added = 0;

    for (const Edge& e : edges) {
        // Добавяме ребро само ако не създава цикъл
        if (!dsu.same(e.u, e.v)) {
            dsu.unite(e.u, e.v);
            total_weight += e.weight;
            edges_added++;
            if (edges_added == n - 1) break; // MST има n-1 ребра
        }
    }
    return total_weight;
}

Обяснение: Проверяваме дали двата върха на реброто са в различни компоненти. Ако са, добавяме реброто, защото то не създава цикъл.

3.2. Свързани компоненти

Броят на свързаните компоненти е равен на броя елементи \(i\), за които parent[i] == i. Това са корените на различните множества.

int countComponents(DSU& dsu, int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (dsu.find(i) == i) {
            count++;
        }
    }
    return count;
}

Алтернативно, можем да поддържаме броя компоненти директно в структурата:

struct DSU_WithCount {
    vector<int> parent, sz;
    int components;

    DSU_WithCount(int n) {
        parent.resize(n + 1);
        sz.resize(n + 1, 1);
        components = n;
        for (int i = 1; i <= n; i++) parent[i] = i;
    }

    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            if (sz[root_i] < sz[root_j]) swap(root_i, root_j);
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
            components--;  // Намалява с 1 при всяко обединяване
        }
    }

    int getComponents() {
        return components;
    }
};

3.3. Динамична свързаност

Можем да добавяме ребра и да проверяваме за път между два върха в реално време. Например, в онлайн заявки:

void processQueries(int n, vector<pair<int,int>>& queries) {
    DSU dsu(n);

    for (auto [type, a, b] : queries) {
        if (type == 1) {
            // Добави ребро между a и b
            dsu.unite(a, b);
        } else {
            // Провери дали a и b са свързани
            if (dsu.same(a, b)) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }
}

3.4. Откриване на цикли

В ненасочен граф можем да откриваме цикли:

bool hasCycle(int n, vector<pair<int,int>>& edges) {
    DSU dsu(n);
    for (auto [u, v] : edges) {
        if (dsu.same(u, v)) {
            return true;  // Намерен е цикъл
        }
        dsu.unite(u, v);
    }
    return false;
}

3.5. Задачи за свързаност на мрежа

Често се използва за задачи тип "дали мрежата е свързана след добавяне/премахване на връзки", "намиране на критични връзки" и т.н.

4. Разширени техники и варианти

4.1. DSU с rollback (Undo операции)

В някои задачи може да се наложи да "отменяме" операции unite. Това изисква малко по-различна имплементация без path compression:

struct DSU_Rollback {
    vector<int> parent, rank;
    stack<pair<int, int>> history;  // История на промени

    DSU_Rollback(int n) {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        for (int i = 1; i <= n; i++) parent[i] = i;
    }

    int find(int i) {
        // Без path compression за да може rollback
        while (parent[i] != i) i = parent[i];
        return i;
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i == root_j) return;

        if (rank[root_i] < rank[root_j]) swap(root_i, root_j);
        history.push({root_j, parent[root_j]});
        parent[root_j] = root_i;

        if (rank[root_i] == rank[root_j]) {
            history.push({root_i, rank[root_i]});
            rank[root_i]++;
        }
    }

    void rollback() {
        // Отменяме последната операция
        if (history.empty()) return;
        auto [node, value] = history.top();
        history.pop();
        // Логика за връщане...
    }
};

4.2. Persistent DSU

Запазва предишни версии на структурата, позволявайки заявки за различни моменти във времето.

4.3. DSU с допълнителна информация

Можем да пазим допълнителна информация за всяко множество:

struct DSU_Extended {
    vector<int> parent, sz;
    vector<long long> sum;  // Сума на елементите в множеството

    DSU_Extended(int n, vector<int>& values) {
        parent.resize(n + 1);
        sz.resize(n + 1, 1);
        sum.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            sum[i] = values[i];
        }
    }

    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            if (sz[root_i] < sz[root_j]) swap(root_i, root_j);
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
            sum[root_i] += sum[root_j];  // Обединяваме сумите
        }
    }

    long long getSum(int i) {
        return sum[find(i)];
    }
};

5. Типични грешки и съвети

5.1. Често срещани грешки

  1. Забравяне на path compression: Води до бавна работа
  2. Неправилно обединяване: Обединяване на елементи вместо техните корени
  3. Индексация: Забравяне че работим с 0-based или 1-based индекси
  4. Рекурсия без base case: Забравяне на проверка if (parent[i] == i)

5.2. Практически съвети

  • Винаги използвайте и двете оптимизации (path compression + union by size/rank)
  • За по-лесно дебъгване, добавете метод print() който показва текущото състояние
  • При задачи с големи числа, внимавайте да не препълните типовете данни
  • Тествайте с малки примери за да проверите коректността

6. Задачи за упражнение

Основни задачи

  1. CSES Road Construction: Поддържане на броя компоненти и размера на най-големия. Много добра задача за начало.
  2. SPOJ MST: Класически MST с алгоритъм на Крускал.
  3. Codeforces 25D: Roads not only in Berland - интересна задача за преструктуриране на граф.

Средни задачи

  1. Codeforces 277A: Learning Languages - задача за свързани компоненти.
  2. CSES Road Reparation: MST с проверка за свързаност.
  3. AtCoder ABC 120D: Bridges - задача за динамична свързаност.

Напреднали задачи

  1. Codeforces 400D: Dima and Bacteria - DSU с допълнителни ограничения.
  2. SPOJ KOZE: Sheep - 2D DSU за свързаност в матрица.
  3. Codeforces 763C: Timofey and rectangles - нестандартно приложение на DSU.

🏁 Заключение

DSU е една от най-важните структури в състезателното програмиране. Тя е: - Изключително бърза: Почти константни операции благодарение на оптимизациите - Лесна за писане: Имплементацията е кратка и ясна - Универсална: Прилага се в огромен брой различни задачи

DSU често е "скритото" решение на задачи, които на пръв поглед не изглеждат свързани с графи. Когато видите задача за групиране на елементи или поддържане на еквивалентност между обекти, помислете за DSU!

Научете добре тази структура - тя ще ви спести много време и ще ви помогне да решавате ефективно сложни проблеми за свързаност и обединяване на множества.