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

Представьте шесть городов 0…5. Город — вершина графа, дорога между двумя городами — ребро. Из 0 в 2 можно попасть по пути 0→1→2, даже без прямой дороги 0—2. Компонента связности — все города, между которыми можно проехать; изолированный город тоже образует компоненту. После появления каждой новой дороги нужно быстро проверять, какие города связаны.

DSU / СНМ (Disjoint-set union) — Структура, поддерживающая разбиение элементов на попарно непересекающиеся множества и операции find и union.

В прошлой лекции мы соединяли списки; теперь нужна другая информация: принадлежат ли элементы одной группе. После дорог 0—1 и 1—2 города 0, 1, 2 образуют одну компоненту. Добавленная 0—2 уже не уменьшит число групп. Проследите эту последовательность в таблице, затем создайте дороги самостоятельно.

Вначале каждый элемент — отдельное множество. find(x) возвращает его представителя. union(x,y) объединяет классы элементов x и y, не меняя остальные.

Можно использовать DSU для добавляемых рёбер графа: чтобы проверить, соединены ли u и v, достаточно сравнить их представителей.

Если union(0,1) и union(1,2) уже выполнены, то 0, 1 и 2 должны иметь одного представителя, даже если ребра (0,2) нет. Это транзитивная связь, а не проверка непосредственного соседства. Повторный union внутри одной компоненты ничего не меняет и не должен уменьшать счётчик компонент.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n
    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != x:
            following = self.parent[x]
            self.parent[x] = root
            x = following
        return root
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.components -= 1
        return True
def component_sizes(n, edges):
    d = DSU(n)
    for a, b in edges:
        d.union(a, b)
    return [d.size[d.find(v)] for v in range(n)]

print(*component_sizes(6, [(0, 1), (1, 2), (3, 4)]))

struct Dsu {parent:Vec<usize>,size:Vec<usize>,components:usize}
impl Dsu {
    fn new(n:usize)->Self {Self{parent:(0..n).collect(),size:vec![1;n],components:n}}
    fn find(&mut self,mut x:usize)->usize {
        let mut root=x;while self.parent[root]!=root {root=self.parent[root];}
        while self.parent[x]!=x {let next=self.parent[x];self.parent[x]=root;x=next;}
        root
    }
    fn union(&mut self,a:usize,b:usize)->bool {
        let(mut a,mut b)=(self.find(a),self.find(b));if a==b{return false;}
        if self.size[a]<self.size[b]{std::mem::swap(&mut a,&mut b);}
        self.parent[b]=a;self.size[a]+=self.size[b];self.components-=1;true
    }
}
fn component_sizes(n:usize,edges:&[(usize,usize)])->Vec<usize>{let mut d=Dsu::new(n);for &(a,b)in edges{d.union(a,b);} (0..n).map(|v|{let root=d.find(v);d.size[root]}).collect()}
fn main(){let result=component_sizes(6,&[(0,1),(1,2),(3,4)]);println!("{}",result.iter().map(|x|x.to_string()).collect::<Vec<_>>().join(" "));}

3 3 3 2 2 1

Контракт определён. Теперь выберем представление, которое позволит объединять компоненты без переписывания всех их элементов.

Разбиение на непересекающиеся множества удобно хранить лесом. У каждой вершины ровно один parent, а корень ссылается сам на себя. Сам номер представителя не важен — важно равенство представителей.

Каждый набор элементов хранится деревом указателей parent. В корне parent[root] = root; он и является представителем. Запрос find поднимается по ссылкам до корня.

makeSet(x):
    parent[x] = x
    rank[x] = 0

find(x):
    if parent[x] == x: return x
    return find(parent[x])

Вызов union сначала вычисляет find для обоих аргументов, затем меняет parent одного корня. Если переподвесить произвольную внутреннюю вершину, можно оторвать часть её старой компоненты или создать цикл. Массив size относится к корням; размер компоненты x читают как size[find(x)].

Лес хранит ответ корректно, но его форма пока может быть плохой. Ограничим высоту правилом объединения.

Наивное объединение позволяет каждый раз подвешивать длинное дерево под новый корень. После n−1 таких операций получится цепочка. Сначала освоим объединение по размеру: корень компоненты из 3 вершин подвесим под корень компоненты из 7, а в новом корне запишем размер 10. Номер корня при этом не важен.

union(a,b):
    a, b = find(a), find(b)
    if a == b: return false
    if size[a] < size[b]: swap(a,b)
    parent[b] = a
    size[a] += size[b]
    return true

Путь вершины становится длиннее только при присоединении её меньшей компоненты к большей. Тогда размер как минимум удваивается: 1, 2, 4, 8… Поэтому без сжатия высота не превосходит O(log n). Ранг — другой способ выбирать направление; его анализ можно прочитать после практики с размером.

Ранг (Rank) — Вспомогательное значение корня, ограничивающее высоту дерева при union по рангу.

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

Следовательно, без сжатия путей один find занимает O(log n). Равноправный вариант — union по размеру: меньший набор под больший.

Для обязательной реализации используйте уже разобранный union по размеру. Ранг — равноправная альтернатива, а строгое исследование оценок одной и двух эвристик вынесено в дополнительные главы. Совместное применение размера и сжатия даёт очень малую амортизированную цену длинной последовательности операций.

Ранги дали логарифмический путь. Используем сам факт прохождения пути, чтобы ускорить следующие запросы.

Ранг ограничивает исходную высоту, но повторный find всё ещё может проходить те же рёбра. Запомним найденный корень прямо в посещённых вершинах: это и есть сжатие путей.

Сжатие путей (Path compression) — После find(x) все вершины пройденного пути начинают непосредственно указывать на найденный корень.

Первый запрос может пройти несколько ссылок, но он ускоряет будущие запросы. Сжатие путей не меняет разбиение на множества: меняется только форма дерева.

find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

Сжатие меняет только ссылки внутри прежней компоненты. После него ранг уже не обязан совпадать с текущей высотой: уменьшать ранги после find не нужно. Итеративный вариант сначала находит корень, затем проходит путь второй раз; он не расходует стек вызовов на длинной наивной цепочке.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n
    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != x:
            following = self.parent[x]
            self.parent[x] = root
            x = following
        return root
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.components -= 1
        return True
d = DSU(6)
for a, b in [(0, 1), (1, 2), (3, 4), (0, 2)]:
    d.union(a, b)
print(d.components, d.size[d.find(2)])

struct Dsu {parent:Vec<usize>,size:Vec<usize>,components:usize}
impl Dsu {
    fn new(n:usize)->Self {Self{parent:(0..n).collect(),size:vec![1;n],components:n}}
    fn find(&mut self,mut x:usize)->usize {
        let mut root=x;while self.parent[root]!=root {root=self.parent[root];}
        while self.parent[x]!=x {let next=self.parent[x];self.parent[x]=root;x=next;}
        root
    }
    fn union(&mut self,a:usize,b:usize)->bool {
        let(mut a,mut b)=(self.find(a),self.find(b));if a==b{return false;}
        if self.size[a]<self.size[b]{std::mem::swap(&mut a,&mut b);}
        self.parent[b]=a;self.size[a]+=self.size[b];self.components-=1;true
    }
}
fn main(){let mut d=Dsu::new(6);for(a,b)in[(0,1),(1,2),(3,4),(0,2)]{d.union(a,b);}let root=d.find(2);println!("{} {}",d.components,d.size[root]);}

3 3

Реализация с двумя эвристиками готова: перейдём к запросам связности и Краскалу. Строгое исследование стоимости последовательности и обратной функции Аккермана доступно в дополнительных главах.

def connected(n, edges, queries):
	# Напишите решение
	pass

Первый этап — запросы связности и размера: добавьте дороги 0—1, 1—2 и 3—4. Теперь find(0)=find(2), но find(0)≠find(3); size[find(2)]=3. Проверьте эти ответы в модели первой главы. Реализуйте component_sizes в разминке практики, а затем переходите к взвешенным дорогам.

Обычные примеры: отслеживание компонент связности при добавлении рёбер, построение минимального остовного дерева алгоритмом Краскала, объединение эквивалентных сущностей.

Для запросов достаточно массивов parent и size со сжатием путей. Теперь второй этап: у дороги есть вес — цена строительства. Цикл — замкнутый путь, который вернулся в начало. Остов — набор дорог, соединяющий все города без циклов; в связном графе из n вершин у него n−1 ребро. Минимальный остов имеет наименьшую сумму весов.

Пусть дороги 0—1, 1—2, 0—2, 2—3 имеют веса 1, 2, 3, 4. Берём первые две: они соединяют разные компоненты. Дорогу 0—2 веса 3 пропускаем: путь через 1 уже есть. Дорога 2—3 соединяет последний город. Получен остов веса 1+2+4=7. Это шаги Краскала: рассматривать рёбра от лёгких к тяжёлым и брать только соединяющие разные компоненты.

В Краскале пропускаем ребро, если его концы уже имеют одного представителя: оно замкнуло бы цикл в выбранном лесу. Иначе добавляем вес и объединяем компоненты. Для несвязного графа получится минимальный остовный лес, а не одно дерево; проверяйте число компонент. Для удаления дороги, восстановления пути или поиска минимального ребра на пути одного DSU недостаточно.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n
    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != x:
            following = self.parent[x]
            self.parent[x] = root
            x = following
        return root
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.components -= 1
        return True
def kruskal(n, edges):
    d, total = DSU(n), 0
    for weight, a, b in sorted(edges):
        if d.union(a, b):
            total += weight
    return total, d.components

print(*kruskal(4, [(4, 0, 1), (1, 1, 2), (2, 0, 2), (3, 2, 3)]))

struct Dsu {parent:Vec<usize>,size:Vec<usize>,components:usize}
impl Dsu {
    fn new(n:usize)->Self {Self{parent:(0..n).collect(),size:vec![1;n],components:n}}
    fn find(&mut self,mut x:usize)->usize {
        let mut root=x;while self.parent[root]!=root {root=self.parent[root];}
        while self.parent[x]!=x {let next=self.parent[x];self.parent[x]=root;x=next;}
        root
    }
    fn union(&mut self,a:usize,b:usize)->bool {
        let(mut a,mut b)=(self.find(a),self.find(b));if a==b{return false;}
        if self.size[a]<self.size[b]{std::mem::swap(&mut a,&mut b);}
        self.parent[b]=a;self.size[a]+=self.size[b];self.components-=1;true
    }
}
fn kruskal(n:usize,edges:&[(i64,usize,usize)])->(i64,usize){let mut edges=edges.to_vec();edges.sort_unstable();let mut d=Dsu::new(n);let mut total=0;for(w,a,b)in edges{if d.union(a,b){total+=w;}}(total,d.components)}
fn main(){let(total,components)=kruskal(4,&[(4,0,1),(1,1,2),(2,0,2),(3,2,3)]);println!("{} {}",total,components);}

6 1

Теперь вы умеете предсказывать число компонент, обновлять размер у представителя и отклонять ребро, создающее цикл. Дальше в основном маршруте — динамическое программирование: граф переходов поможет упорядочить подзадачи. Сливаемые кучи доступны отдельным продвинутым модулем.

def component_sizes(n, edges):
	# Напишите решение
	pass

Справочник собирает определения из разобранных разделов. Используйте поиск, если нужно восстановить термин; затем переходите к оценке ограничений и задачам для самостоятельного решения.

Общий справочник всех лекций ↗

Найдено: 12 из 12

Сначала подставьте максимальные размеры из условия в оценку времени и памяти. Оценка числа действий — ориентир: константы, язык и ввод проверяются отдельно.

Учитываем сумму размеров групп

Пусть S — сумма численностей всех групп. Объединяйте каждого участника с первым: O(S) вызовов union. Попарные связи потребовали бы сумму kᵢ², которая может быть огромной даже при S ≤ 500 000. Инициализация массивов стоит O(n).

Оценка DSU не отменяет сортировку

Для m рёбер Краскал требует O(m log(m+1)) на сортировку и O(m α(n)) на DSU. Именно сортировка обычно доминирует. При m = 200 000 это несколько миллионов сравнений вместо многократного обхода графа.

Сумма весов может достигнуть (n−1)·maxWeight. При n = 200 000 и весах до 10⁹ нужен 64-битный тип. Отрицательные веса не мешают Краскалу, а несвязный граф требует явно договориться об ответе: лес или ошибка отсутствия остова.

Когда обычный DSU не подходит

Удаление произвольного ребра не выражается обратным union: внутри компоненты может быть много альтернативных путей. Офлайн-удаления иногда обрабатывают в обратном порядке; для откатов нужна другая реализация, обычно без сжатия путей.

В тестах нужны изолированные вершины, повторное ребро, union внутри одной компоненты, длинная последовательность объединений и повторный find. Проверяйте разбиение, а не конкретный номер корня: корректные реализации выбирают разные представители.

Разминка: реализуйте операции, затем размеры

Сначала напишите find со сжатием и union по размеру. Затем используйте тот же инвариант для размеров компонент. Проверьте изолированную вершину, повторное ребро и цикл до перехода к внешним задачам.

def dsu_operations(n, ops):
	# parent, size; затем find и union
	pass

def group_sizes(n, edges):
	# Напишите DSU с parent и size
	pass

Основное применение

Начните с Find if Path Exists in Graph и News Distribution. Accounts Merge добавляет отображение строк в id; задачи о циклах и остове используйте после разбора городов и дорог. Трудное испытание в списке необязательно для первого прохода.

Примените разобранные приёмы самостоятельно. Для каждой задачи сначала сформулируйте требования к ответу и предложите простое решение. Затем подставьте максимальные ограничения, оцените время и память и решите, какое улучшение требуется. Подсказки с идеей и оценкой раскрываются отдельно.

Уровни задают порядок практики в курсе, а не единую шкалу платформ. Если уровень отличается от отметки LeetCode, это указано в карточке. Для Codeforces используется оценка курса.

Дальше в динамическом программировании граф зависимостей поможет выбирать порядок подзадач. Сливаемые кучи доступны как отдельный продвинутый модуль.