DSU | kz-maxx

DSU деген не?

DSU — бірнеше элементті топтарға бөліп сақтау структурасы. Толық аты: Disjoint Set Union.

DSU екі негізгі операция жасайды:

find(v) — v қай топта екенін табу
unite(a, b) — a және b тұрған топтарды біріктіру

DSU графтағы компоненттермен жұмыс істеуге өте ыңғайлы. Мысалы, екі вершина бір компонентте ме, жоқ па — тез тексереді.

Қай жерде қолданылады?

компоненттерді біріктіру
екі вершина connected пе тексеру
графта цикл бар ма тексеру
Kruskal алгоритмі
минималды остовное дерево
online connectivity задачалары

Негізгі идея

Әр элементтің parent деген мәні болады.

parent[v]

Бұл v элементінің ата-анасы. Егер:

parent[v] == v

онда v — өз тобының басты вершинасы, яғни root.

root — компонентаның басты өкілі
бір компоненттегі барлық вершина бір root-қа келеді

Басында не болады?

Басында әр элемент жеке компонент болады.

1 бөлек
2 бөлек
3 бөлек
4 бөлек

Сондықтан:

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

Мұнда sz[i] — компонентаның size-ы.

find функциясы

find(v) — v элементінің root-ын табады.

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

    return find(parent[v]);
}

Егер v өзі root болса, оны қайтарамыз. Әйтпесе parent арқылы жоғары көтерілеміз.

Path Compression

Жай find баяу болуы мүмкін. Сондықтан path compression қолданамыз.

Идея:

find(v) жасағанда
v-дан root-қа дейінгі барлық вершина
бірден root-қа жалғанады

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

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

Бұл DSU-ды өте жылдам қылады.

unite функциясы

unite(a, b) — a және b тұрған компоненттерді біріктіреді.

Алдымен олардың root-ын табамыз:

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

Егер root бірдей болса, олар бір компонентте тұр.

if (a == b) {
    return;
}

Егер әртүрлі болса, біреуін екіншісіне қосамыз:

parent[b] = a;

Union by Size

Үлкен компонентке кішісін қосқан жақсы. Бұл union by size деп аталады.

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];
}

Мұнда кіші компонент үлкен компонентке қосылады.

Толық DSU шаблоны

const int N = 100010;

int parent[N];
int sz[N];

void make_set(int v) {
    parent[v] = v;
    sz[v] = 1;
}

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

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

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];
}

Екі вершина бір компонентте ме?

Екі вершина бір компонентте екенін тексеру үшін олардың root-ын салыстырамыз:

if (find(a) == find(b)) {
    cout << "YES";
} else {
    cout << "NO";
}

root бірдей → бір компонент
root әртүрлі → әртүрлі компонент

Задача 1: компоненттерді біріктіру

n элемент және q сұраныс берілген.

Сұраныстар:

union a b — a және b компоненттерін біріктіру
get a b — a және b бір компонентте ме тексеру

Input

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

Output

YES
NO
YES

Толық реализация

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

const int N = 100010;

int n, q;
int parent[N];
int sz[N];

void make_set(int v) {
    parent[v] = v;
    sz[v] = 1;
}

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

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

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];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        make_set(i);
    }

    while (q--) {
        string type;
        int a, b;

        cin >> type >> a >> b;

        if (type == "union") {
            unite(a, b);
        } else {
            if (find(a) == find(b)) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }

    return 0;
}

Компонента size-ын табу

Егер біз union by size қолдансақ, онда root-та компонентаның size-ы сақталады.

v тұрған компонентаның size-ын табу:

int get_size(int v) {
    v = find(v);
    return sz[v];
}

Мысалы:

cout << get_size(3);

Задача 2: компонент size

Сұраныстар:

union a b — біріктіру
size v — v тұрған компонентаның size-ын шығару

Input

5 5
union 1 2
size 1
union 2 3
size 1
size 4

Output

2
3
1

Компонента size коды

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

const int N = 100010;

int n, q;
int parent[N];
int sz[N];

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

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

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];
}

int get_size(int v) {
    v = find(v);
    return sz[v];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;

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

    while (q--) {
        string type;
        cin >> type;

        if (type == "union") {
            int a, b;
            cin >> a >> b;

            unite(a, b);
        } else {
            int v;
            cin >> v;

            cout << get_size(v) << '\n';
        }
    }

    return 0;
}

DSU арқылы цикл табу

Неориентированный графта цикл бар ма тексеруге DSU қолдануға болады.

Әр ребро a -- b үшін:

егер find(a) == find(b)
онда a және b бұрыннан бір компонентте
осы ребро cycle жасайды

if (find(a) == find(b)) {
    hasCycle = true;
} else {
    unite(a, b);
}

Задача 3: графта цикл бар ма?

Неориентированный граф берілген. Онда цикл бар ма, соны тексеру керек.

Input

Output

YES

Цикл табу толық коды

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

const int N = 100010;

int n, m;
int parent[N];
int sz[N];

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

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

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];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

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

    bool hasCycle = false;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        if (find(a) == find(b)) {
            hasCycle = true;
        } else {
            unite(a, b);
        }
    }

    if (hasCycle) {
        cout << "YES";
    } else {
        cout << "NO";
    }

    return 0;
}

Компоненттер санын сақтау

Басында әр вершина жеке компонент:

int components = n;

Егер екі әртүрлі компонентті біріктірсек, компонент саны 1-ге азаяды:

if (a != b) {
    components--;
}

Компонент саны бар unite

int components;

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];
    components--;
}

Kruskal алгоритмі және DSU

Kruskal — минималды остовное дерево табатын алгоритм. Ол DSU арқылы жұмыс істейді.

Идея:

барлық реброны weight бойынша сорттаймыз
ең кіші реброларды қараймыз
егер ребро cycle жасамаса, оны аламыз
DSU арқылы компоненттерді біріктіреміз

Kruskal қысқа коды

struct Edge {
    int a;
    int b;
    int w;
};

vector<Edge> edges;

sort(edges.begin(), edges.end(), [](Edge x, Edge y) {
    return x.w < y.w;
});

long long ans = 0;

for (Edge e : edges) {
    if (find(e.a) != find(e.b)) {
        unite(e.a, e.b);
        ans += e.w;
    }
}

Задача 4: минималды остовное дерево

Неориентированный weighted graph берілген. Минималды остовное дерево weight суммасын табу керек.

Input

Output

Таңдалатын ребролар:

2 -- 3 weight 1
1 -- 3 weight 2
2 -- 4 weight 3
сумма = 6

Kruskal толық реализация

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

const int N = 100010;

struct Edge {
    int a;
    int b;
    int w;
};

int n, m;
int parent[N];
int sz[N];
vector<Edge> edges;

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

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

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];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

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

    for (int i = 1; i <= m; i++) {
        int a, b, w;
        cin >> a >> b >> w;

        edges.push_back({a, b, w});
    }

    sort(edges.begin(), edges.end(), [](Edge x, Edge y) {
        return x.w < y.w;
    });

    long long ans = 0;

    for (Edge e : edges) {
        if (find(e.a) != find(e.b)) {
            unite(e.a, e.b);
            ans += e.w;
        }
    }

    cout << ans;

    return 0;
}

Union by Rank

Кейде union by size орнына union by rank қолданылады.

rank — деревоның шамамен биіктігі.

int parent[N];
int rnk[N];

void unite(int a, int b) {
    a = find(a);
    b = find(b);

    if (a == b) {
        return;
    }

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

    parent[b] = a;

    if (rnk[a] == rnk[b]) {
        rnk[a]++;
    }
}

Практикада көбіне union by size оңайырақ.

DSU vs DFS/BFS

Метод	Қайда ыңғайлы	Ерекшелігі
DFS/BFS	граф дайын тұрғанда компонент табу	бір рет обход жасау
DSU	ребролар біртіндеп қосылғанда	біріктіру және тексеру өте тез

Асимптотика

Операция	Уақыт
find	шамамен O(1)
unite	шамамен O(1)
q сұраныс	шамамен O(q)

Нақты теориялық күрделілік O(α(n)). Бірақ практикада бұл почти O(1) сияқты жұмыс істейді.

Қысқа шаблон

const int N = 100010;

int parent[N];
int sz[N];

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

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

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];
}

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