Деревья и графы. Система непересекающихся множеств. Поиск наименьшего общего предка.
Система непересекающихся множеств
Структура данных "система непересекающихся множеств" (на английском "disjoint-set-union", или просто "DSU").
Эта структура данных предоставляет следующие возможности. Изначально имеется несколько элементов, каждый из которых находится в отдельном (своём собственном) множестве. За одну операцию можно объединить два каких-либо множества, а также можно запросить, в каком множестве сейчас находится указанный элемент. Также, в классическом варианте, вводится ещё одна операция — создание нового элемента, который помещается в отдельное множество.
Таким образом, базовый интерфейс данной структуры данных состоит всего из трёх операций:
- make_set(x) — добавляет новый элемент $x$, помещая его в новое множество, состоящее из одного него.
- union_sets(x,y) — объединяет два указанных множества (множество, в котором находится элемент $x$, и множество, в котором находится элемент $y$).
- find_set(x) - возвращает, в каком множестве находится указанный элемент $x$. На самом деле при этом возвращается один из элементов множества (называемый представителем или лидером (в англоязычной литературе "leader")). Этот представитель выбирается в каждом множестве самой структурой данных (и может меняться с течением времени, а именно, после вызовов union_sets()). Например, если вызов find_set() для каких-то двух элементов вернул одно и то же значение, то это означает, что эти элементы находятся в одном и том же множестве, а в противном случае — в разных множествах.
Описываемая ниже структура данных позволяет делать каждую из этих операций почти за $O(1)$ в среднем (более подробно об асимптотике см. ниже после описания алгоритма).
Реализация на Python
# DSU (система непересекающихся множеств): сжатие путей и объединение по размеру, O(α(n)) амортизированно
def make_set(parent, set_size, x):
"""Добавляет элемент x в новое множество из одного элемента."""
if x in parent:
return
parent[x] = x
set_size[x] = 1
def find_set(parent, x):
"""Возвращает представителя множества, в котором лежит x; по пути сжимает цепочку."""
if parent[x] != x:
parent[x] = find_set(parent, parent[x])
return parent[x]
def union_sets(parent, set_size, x, y):
"""Объединяет множества элементов x и y: меньшее подвешивается к большему."""
root_x = find_set(parent, x)
root_y = find_set(parent, y)
if root_x == root_y:
return
if set_size[root_x] < set_size[root_y]:
root_x, root_y = root_y, root_x
parent[root_y] = root_x
set_size[root_x] += set_size[root_y]
if __name__ == "__main__":
parent, set_size = {}, {}
for x in range(1, 7):
make_set(parent, set_size, x)
union_sets(parent, set_size, 1, 2)
union_sets(parent, set_size, 3, 4)
union_sets(parent, set_size, 2, 4)
print(find_set(parent, 1) == find_set(parent, 3)) # True
print(find_set(parent, 5) == find_set(parent, 1)) # False
print(set_size[find_set(parent, 1)]) # 4
Реализация на Rust
// DSU (система непересекающихся множеств): сжатие путей и объединение по размеру, O(α(n)) амортизированно
use std::collections::HashMap;
#[derive(Default)]
pub struct Dsu {
parent: HashMap<usize, usize>,
set_size: HashMap<usize, usize>, // размер множества хранится только у его представителя
}
impl Dsu {
// Добавляет элемент x в новое множество из одного элемента: O(1) в среднем
pub fn make_set(&mut self, x: usize) {
if !self.parent.contains_key(&x) {
self.parent.insert(x, x);
self.set_size.insert(x, 1);
}
}
// Возвращает представителя множества x; по пути сжимает цепочку родителей
pub fn find_set(&mut self, x: usize) -> usize {
let up = self.parent[&x];
if up == x {
return x;
}
let root = self.find_set(up);
self.parent.insert(x, root);
root
}
// Объединяет множества элементов x и y: меньшее подвешивается к большему
pub fn union_sets(&mut self, x: usize, y: usize) {
let (mut root_x, mut root_y) = (self.find_set(x), self.find_set(y));
if root_x == root_y {
return;
}
if self.set_size[&root_x] < self.set_size[&root_y] {
std::mem::swap(&mut root_x, &mut root_y);
}
self.parent.insert(root_y, root_x);
let added = self.set_size[&root_y];
*self.set_size.get_mut(&root_x).unwrap() += added;
}
// Размер множества, в котором лежит x
pub fn size_of(&mut self, x: usize) -> usize {
let root = self.find_set(x);
self.set_size[&root]
}
}
fn main() {
let mut dsu = Dsu::default();
for x in 1..=6 { dsu.make_set(x); }
dsu.union_sets(1, 2);
dsu.union_sets(3, 4);
dsu.union_sets(2, 4);
println!("{}", dsu.find_set(1) == dsu.find_set(3)); // true
println!("{}", dsu.find_set(5) == dsu.find_set(1)); // false
println!("{}", dsu.size_of(1)); // 4
}Реализация на C++
// DSU (система непересекающихся множеств): сжатие путей и объединение по размеру, O(α(n)) амортизированно
#include <iostream>
#include <unordered_map>
#include <utility>
struct Dsu {
std::unordered_map<int, int> parent;
std::unordered_map<int, int> set_size; // размер множества хранится только у его представителя
// Добавляет элемент x в новое множество из одного элемента: O(1) в среднем
void make_set(int x) {
if (parent.count(x)) return;
parent[x] = x;
set_size[x] = 1;
}
// Возвращает представителя множества x; по пути сжимает цепочку родителей
int find_set(int x) {
int up = parent.at(x);
if (up == x) return x;
int root = find_set(up);
parent[x] = root;
return root;
}
// Объединяет множества элементов x и y: меньшее подвешивается к большему
void union_sets(int x, int y) {
int root_x = find_set(x);
int root_y = find_set(y);
if (root_x == root_y) return;
if (set_size.at(root_x) < set_size.at(root_y)) std::swap(root_x, root_y);
parent[root_y] = root_x;
set_size[root_x] += set_size[root_y];
}
// Размер множества, в котором лежит x
int size_of(int x) { return set_size.at(find_set(x)); }
};
int main() {
Dsu dsu;
for (int x = 1; x <= 6; ++x) dsu.make_set(x);
dsu.union_sets(1, 2);
dsu.union_sets(3, 4);
dsu.union_sets(2, 4);
int root1 = dsu.find_set(1);
int root3 = dsu.find_set(3);
std::cout << std::boolalpha << (root1 == root3) << '\n'; // true
std::cout << (dsu.find_set(5) == root1) << '\n'; // false
std::cout << dsu.size_of(1) << '\n'; // 4
return 0;
}