kz-maxx

RU KZ
← Главная

DSU (Disjoint Set Union)

Система непересекающихся множеств

Что такое DSU?

DSU — это структура данных, которая быстро отвечает на два вопроса:

  • находятся ли два элемента в одном множестве
  • как объединить два множества
Главная идея — каждое множество хранится как дерево.

Когда используется?

  • Компоненты связности
  • Алгоритм Краскала
  • Проверка связности
  • Offline-запросы
  • Объединение групп

Главная идея

Каждый элемент знает своего родителя.

1 → 1 2 → 1 3 → 1 4 → 4 5 → 4

Здесь есть два множества:

{1,2,3} {4,5}

Массив parent

int parent[N];

parent[x] — родитель вершины.

Если 

parent[x] == x

то x является корнем множества.

Инициализация

Сначала каждый элемент находится сам по себе. 

for (int i = 1; i <= n; i++) {
    parent[i] = i;
}

Получается:

1 2 3 4 5

Функция find()

find(x) возвращает корень множества. 

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

    return find(parent[x]);
}

Пример:

1 ↓ 2 ↓ 3

find(3) вернет 1.

Сжатие путей

После первого find дерево можно сделать короче. 

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

    return parent[x] = find(parent[x]);
}

Было:

1 ↓ 2 ↓ 3 ↓ 4

После find(4):

1 ↙ ↓ ↘ 2 3 4
Это называется Path Compression.

Объединение множеств

Чтобы объединить два множества: 

void unite(int a, int b) {

    a = find(a);
    b = find(b);

    if (a != b) {
        parent[b] = a;
    }

}

Пример объединения

Было:

1 2 3 4

unite(1,2)

1 ↓ 2

unite(2,3)

1 ↓ 2 ↓ 3

Теперь 

find(3) == 1

Задача 1

Есть n элементов. Нужно выполнять два типа запросов.

union a b get a b

get должен вывести YES, если вершины находятся в одном множестве.

Input

5 5
union 1 2
union 2 3
get 1 3
get 1 5
get 4 5

Output

YES
NO
NO

Полная реализация

#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

int parent[N];

int find(int x) {

    if (parent[x] == x) {
        return x;
    }

    return parent[x] = find(parent[x]);

}

void unite(int a, int b) {

    a = find(a);
    b = find(b);

    if (a != b) {
        parent[b] = a;
    }

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;

    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    while (q--) {

        string op;
        int a, b;

        cin >> op >> a >> b;

        if (op == "union") {
            unite(a, b);
        }

        else {

            if (find(a) == find(b)) {
                cout << "YES\n";
            }

            else {
                cout << "NO\n";
            }

        }

    }

}

Объединение по размеру

Можно хранить размер каждого множества. 

int sz[N];

При объединении маленькое дерево цепляется к большому. 

void unite(int a, int b) {

    a = find(a);
    b = find(b);

    if (a == b) {
        return;
    }

    if (sz[a] < sz[b]) {
        swap(a, b);
    }

    parent[b] = a;
    sz[a] += sz[b];

}
Так дерево становится намного ниже.

Размер множества

После объединений размер множества хранится только у корня. 

sz[find(x)]

Например:

1 2 3 ↓ корень = 1 sz[1] = 3

Задача 2

После каждого объединения вывести размер множества.

Input

5 3
1 2
2 3
4 5

Output

2
3
2

DSU + Краскал

DSU используется в алгоритме Краскала.

Если две вершины находятся в разных множествах, то ребро можно добавить. 

if (find(a) != find(b)) {

    unite(a, b);

}

Асимптотика

Операция Время
find() O(α(n))
union() O(α(n))
α(n) — обратная функция Аккермана. На практике считается почти O(1).

Краткий шаблон

int parent[N];

int find(int x) {

    if (parent[x] == x) {
        return x;
    }

    return parent[x] = find(parent[x]);

}

void unite(int a, int b) {

    a = find(a);
    b = find(b);

    if (a != b) {
        parent[b] = a;
    }

}