Cегодня разбираем Систему Непересекающихся Множеств (СНМ), или же Disjoint Set Union (DSU)
Идея
Система Непересекающихся Множеств - это структура данных, предназначенная для работы с разбиением элементов на непересекающиеся группы. Она поддерживает две основные операции:
1. Объединить две группы в одну.
2. Определить, принадлежат ли два элемента одной группе.
Особенности
1. Каждый элемент имеет ссылку на своего "родителя"
2. Элемент, ссылающийся сам на себя, является корнем (лидером) множества
3. Два элемента находятся в одном множестве, если у них одинаковый корень
4. Для ускорения операций используются две оптимизации:
- Сжатие путей: при поиске корня все элементы на пути перенаправляются к корню
- Весовая эвристика: при объединении меньшее множество присоединяется к большему
Код (C++)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 10;
int dsu[MAXN];
int sz[MAXN];
int root(int v) {
if (dsu[v] == v) return v;
return dsu[v] = root(dsu[v]);
}
int unite(int u, int v) {
u = root(u);
v = root(v);
if (u == v) {
return 0;
}
if (sz[v] < sz[u]) {
swap(u, v);
}
dsu[u] = v;
sz[v] += sz[u];
return 1;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
dsu[i] = i;
sz[i] = 1;
}
for (int i = 0; i < m; i++) {
int a, b;
char op;
cin >> a >> b >> op;
if (op == '?') {
if (root(a) == root(b)) {
cout << "YES\n";
} else {
cout << "NO\n";
}
} else if (op == '+') {
unite(a, b);
}
}
}
Где применять?
- Построение минимального остовного дерева (алгоритм Краскала)
- Проверка связности графа
- Нахождение компонент связности
- Добавление рёбер и проверка появления циклов
- Постепенное объединение компонент
- Задачи на оффлайн-обработку
- Объединение интервалов и отрезков
- Работа с эквивалентностями и отношениями
- Задачи на перестановки и циклические сдвиги
@postupashki_prog