СНМ (DSU) - структура для объединения и поиска компонент
def leader(v):
if p[v] == v:
return v
p[v] = leader(p[v])
return p[v]
def unite(a, b):
a = leader(a)
b = leader(b)
if s[a] > s[b]:
a, b = b, a
s[b] += s[a]
p[a] = b
p = list(range(n))
s = [1] * n#include <bits/stdc++.h>
using namespace std;
vector<int> p, sz;
int leader(int v) {
if (p[v] == v) return v;
return p[v] = leader(p[v]);
}
void unite(int a, int b) {
a = leader(a);
b = leader(b);
if (sz[a] > sz[b]) swap(a, b);
sz[b] += sz[a];
p[a] = b;
}
int main() {
int n;
cin >> n;
p.resize(n);
sz.resize(n, 1);
for (int i = 0; i < n; i++) {
p[i] = i;
}
// Пример использования
unite(0, 1);
unite(2, 3);
unite(1, 2);
for (int i = 0; i < n; i++) {
cout << leader(i) << " ";
}
return 0;
}СНМ (Disjoint Set Union, DSU) — это структура данных, которая эффективно поддерживает операции объединения двух множеств и поиска представителя (лидера) множества.
Основные операции:
Изначально каждая вершина находится в своём собственном множестве, её лидер — она сама, а размер множества равен 1.
Благодаря двум эвристикам (сжатие пути и объединение по размеру) операции работают практически за константное время.
Временная сложность: O(α(n)) на операцию, где α(n) — обратная функция Аккермана (практически константа).
Пространственная сложность: O(n) для хранения массивов parent и size.
Рассмотрим объединение вершин 0-1, 2-3, затем 1-2:
Инициализация: p = [0, 1, 2, 3, 4, 5], sz = [1, 1, 1, 1, 1, 1], n=6
unite(0, 1):
leader(0)=0, leader(1)=1
sz[0]=1, sz[1]=1 → присоединяем 0 к 1
p[0]=1, sz[1]=2
unite(2, 3):
leader(2)=2, leader(3)=3
присоединяем 2 к 3
p[2]=3, sz[3]=2
unite(1, 2):
leader(1)=1, leader(2)=3
sz[1]=2, sz[3]=2 → присоединяем 1 к 3
p[1]=3, sz[3]=4
Результат: leader(0)=3, leader(1)=3, leader(2)=3, leader(3)=3, leader(4)=4, leader(5)=5
Множества: {0,1,2,3} и {4}, {5}Введите запросы (1 a b — объединить, 2 a b — проверить, в одном ли множестве):