15.1 Структура Union-Find¶

Что это за структура¶

Union-Find (её также называют DSU — Disjoint Set Union, «система непересекающихся множеств») — это структура данных, которая поддерживает работу с набором элементов, разбитых на отдельные группы.

Она умеет быстро отвечать на два ключевых вопроса:

находятся ли два элемента в одной группе;
как объединить две группы в одну.

Это одна из самых полезных структур в графовых алгоритмах. В книге она идёт сразу после алгоритма Краскала не случайно: именно Union-Find позволяет быстро проверять, соединит ли новое ребро две разные компоненты или создаст цикл.

Интуиция¶

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

команда 1 объединяется с командой 4;
команда 2 объединяется с командой 3;
затем эти крупные группы могут объединиться между собой.

Нам хочется уметь быстро отвечать:

«Элементы a и b уже в одной группе?»
«Объедини группы, в которых находятся a и b».

Хранить все элементы каждой группы явно можно, но это неудобно и медленно. Гораздо эффективнее хранить для каждого элемента ссылку на родителя, а у каждой группы иметь представителя — корень дерева.

Представление через деревья¶

Каждое множество будем хранить как дерево.

У каждого элемента есть родитель.
У корня родитель — он сам.
Корень и есть представитель множества.

Например, если элементы 1, 4, 7 находятся в одном множестве, а 4 — представитель, то связи могут выглядеть так:

flowchart TD
    n1[1] --> n4[4]
    n7[7] --> n4[4]
    n4 --> n4

Hold "Ctrl" to enable pan & zoom

Если элементы 2, 3, 6, 8 лежат в другом множестве, можно получить такую картину:

flowchart TD
    n6[6] --> n3[3]
    n8[8] --> n2[2]
    n3 --> n2
    n2 --> n2

Hold "Ctrl" to enable pan & zoom

Чтобы понять, в каком множестве находится элемент, мы поднимаемся по ссылкам к корню.

Например:

для 6 идём 6 -> 3 -> 2;
значит, представитель элемента 6 — это 2.

Если два элемента имеют одного и того же представителя, они лежат в одном множестве.

Базовые операции¶

1. `find(x)`¶

Возвращает представителя множества, в котором находится элемент x.

Идея очень простая: пока элемент не является корнем, поднимаемся вверх.

2. `same(a, b)`¶

Проверяет, принадлежат ли элементы a и b одному множеству.

Это просто сравнение:

если find(a) == find(b), то множество одно и то же;
иначе множества разные.

3. `unite(a, b)`¶

Объединяет два множества в одно.

Для этого:

находим представителей a и b;
если они уже одинаковые, ничего делать не нужно;
иначе один корень подвешиваем к другому.

Почему нельзя объединять как попало¶

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

Например:

flowchart TD
    n1[1] --> n2[2]
    n2 --> n3[3]
    n3 --> n4[4]
    n4 --> n5[5]
    n5 --> n5

Hold "Ctrl" to enable pan & zoom

Тогда операция find(1) будет проходить почти по всей цепочке. Если таких запросов много, структура станет медленной.

Поэтому нужна хорошая стратегия объединения.

Объединение по размеру¶

В книге предлагается простой и очень полезный приём: всегда присоединять меньшее множество к большему. Именно эта идея и даёт хорошую асимптотику: длина цепочек остаётся порядка O(log n) fileciteturn1file2.

Почему это работает интуитивно:

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

Если размер каждый раз хотя бы удваивается, то максимум таких удвоений — log n.

Базовая реализация DSU на C++¶

Ниже — версия, очень близкая к идее из книги: массив родителя и массив размера.

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

struct DSU {
    vector<int> parent;
    vector<int> sz;

    DSU(int n) {
        parent.resize(n + 1);
        sz.assign(n + 1, 1);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        while (x != parent[x]) {
            x = parent[x];
        }
        return x;
    }

    bool same(int a, int b) {
        return find(a) == find(b);
    }

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

        if (a == b) return false;

        if (sz[a] < sz[b]) swap(a, b);

        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

Что здесь важно¶

parent[x] — родитель элемента x;
если parent[x] == x, то x — корень;
sz[x] имеет смысл только для корней и хранит размер множества;
unite возвращает true, если произошло реальное объединение, и false, если элементы уже были в одном множестве.

Это очень удобно в задачах на графы.

Более быстрая версия: path compression¶

На практике почти всегда используют ещё одно улучшение: сжатие путей (path compression).

Идея такая:

когда мы ищем корень для x, мы поднимаемся по цепочке;
после того как корень найден, мы сразу перенаправляем все вершины на пути прямо к корню.

Например, было так:

flowchart TD
    n6[6] --> n3[3]
    n3 --> n2[2]
    n2 --> n2

Hold "Ctrl" to enable pan & zoom

После вызова find(6) можно сделать так:

flowchart TD
    n6[6] --> n2[2]
    n3[3] --> n2[2]
    n2 --> n2

Hold "Ctrl" to enable pan & zoom

Теперь будущие запросы будут работать быстрее.

Реализация с path compression¶

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

struct DSU {
    vector<int> parent;
    vector<int> sz;

    DSU(int n) {
        parent.resize(n + 1);
        sz.assign(n + 1, 1);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }

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

    bool same(int a, int b) {
        return find(a) == find(b);
    }

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

        if (a == b) return false;

        if (sz[a] < sz[b]) swap(a, b);

        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

Асимптотика¶

Версия из книги¶

Если использовать только объединение меньшего множества к большему, то:

find работает за O(log n);
same работает за O(log n);
unite работает за O(log n).

Именно такая оценка дана в исходном разделе fileciteturn1file2.

Современная версия¶

Если добавить ещё и path compression, то амортизированная сложность становится практически константной:

O(alpha(n)), где alpha — обратная функция Аккермана.

На практике это означает: операция работает почти как O(1) даже на очень больших входных данных.

Пошаговый пример¶

Пусть есть 8 элементов.

Сначала каждый в своём множестве:

{1}
{2}
{3}
{4}
{5}
{6}
{7}
{8}

Выполним операции:

unite(1, 4)
unite(7, 4)
unite(2, 3)
unite(6, 3)
unite(8, 2)
unite(1, 6)

После первых пяти операций получаем примерно такие группы:

{1, 4, 7}
{2, 3, 6, 8}
{5}

После unite(1, 6) объединяются первые две группы, и получаем:

{1, 2, 3, 4, 6, 7, 8}
{5}

Теперь:

same(7, 3) = true
same(5, 1) = false

Где применяется Union-Find¶

1. Алгоритм Краскала¶

Это главное классическое применение.

Когда мы перебираем рёбра в порядке неубывания веса, нужно быстро понимать:

соединяет ли ребро две разные компоненты;
или оно образует цикл.

Если концы ребра лежат в разных множествах — ребро можно брать и объединять компоненты.

2. Поиск компонент связности в офлайн-режиме¶

Если рёбра постепенно добавляются, DSU отлично отслеживает, какие вершины уже соединены.

3. Проверка достижимости¶

После серии объединений можно быстро отвечать, лежат ли две вершины в одной компоненте.

4. Объединение объектов по условию¶

Например:

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

Пример задачи¶

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

Такую задачу удобно решать через DSU:

при чтении ребра u, v делаем unite(u, v);
после этого проверяем same(1, n).

Код¶

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

struct DSU {
    vector<int> parent, sz;

    DSU(int n) {
        parent.resize(n + 1);
        sz.assign(n + 1, 1);
        for (int i = 1; i <= n; i++) parent[i] = i;
    }

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

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }

    bool same(int a, int b) {
        return find(a) == find(b);
    }
};

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

    int n, m;
    cin >> n >> m;

    DSU dsu(n);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        dsu.unite(u, v);

        if (dsu.same(1, n)) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

Пример: использование в Краскале (подробнее про него в следующей главе)¶

Ниже — короткий шаблон того, как DSU встраивается в алгоритм Краскала.

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

struct DSU {
    vector<int> parent, sz;

    DSU(int n) {
        parent.resize(n + 1);
        sz.assign(n + 1, 1);
        for (int i = 1; i <= n; i++) parent[i] = i;
    }

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

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

struct Edge {
    int u, v, w;

    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

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

    int n, m;
    cin >> n >> m;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    sort(edges.begin(), edges.end());

    DSU dsu(n);
    long long ans = 0;
    vector<Edge> mst;

    for (auto e : edges) {
        if (dsu.unite(e.u, e.v)) {
            ans += e.w;
            mst.push_back(e);
        }
    }

    if ((int)mst.size() != n - 1) {
        cout << "NO MST\n";
    } else {
        cout << ans << "\n";
    }
}

Типичные ошибки¶

Ошибка 1. Забыли вызвать `find` перед объединением¶

Нельзя писать так:

parent[b] = a

если a и b — не корни. Сначала обязательно нужно сделать:

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

Иначе дерево структуры может стать некорректным.

Ошибка 2. Не проверили, что множества уже совпадают¶

Если a и b уже в одном множестве, повторное объединение не нужно.

Ошибка 3. Перепутали индексацию¶

Часто вершины во входных данных нумеруются с 1, а иногда с 0. DSU надо согласовать с этим заранее.

Ошибка 4. Хранят размер не только у корней¶

sz[x] имеет смысл только для представителя. После объединения обновлять нужно размер нового корня.

Ошибка 5. Используют DSU там, где нужны удаления¶

Union-Find прекрасно работает на добавлении связей, но не умеет эффективно поддерживать удаление ребра из компоненты.

Что важно запомнить¶

DSU хранит разбиение элементов на непересекающиеся множества.
Каждый элемент ведёт к представителю своего множества.
find(x) находит представителя.
same(a, b) проверяет, одно ли множество.
unite(a, b) объединяет множества.
Если подвешивать меньшее дерево к большему, получаем хорошую эффективность.
Если добавить path compression, операции становятся почти константными на практике.

Короткое резюме¶

Структура Union-Find — это один из самых полезных инструментов в олимпиадном программировании. Она очень проста по идее:

каждая группа хранится как дерево;
у дерева есть корень-представитель;
объединения происходят через соединение корней.

Но при этой простоте она решает очень серьёзные задачи: от поиска компонент связности до построения минимального остовного дерева.

Если ты хорошо освоишь DSU, то начнёшь узнавать целый класс задач, где решение буквально сводится к двум строчкам:

if (!same(a, b)) unite(a, b);

И это один из тех случаев, когда маленькая структура данных даёт очень большую силу.

15.1 Структура Union-Find¶

Что это за структура¶

Интуиция¶

Представление через деревья¶

Базовые операции¶

1. find(x)¶

2. same(a, b)¶

3. unite(a, b)¶

Почему нельзя объединять как попало¶

Объединение по размеру¶

Базовая реализация DSU на C++¶

Что здесь важно¶

Более быстрая версия: path compression¶

Реализация с path compression¶

Асимптотика¶

Версия из книги¶

Современная версия¶

Пошаговый пример¶

Где применяется Union-Find¶

1. Алгоритм Краскала¶

2. Поиск компонент связности в офлайн-режиме¶

3. Проверка достижимости¶

4. Объединение объектов по условию¶

Пример задачи¶

Код¶

Пример: использование в Краскале (подробнее про него в следующей главе)¶

Типичные ошибки¶

Ошибка 1. Забыли вызвать find перед объединением¶

Ошибка 2. Не проверили, что множества уже совпадают¶

Ошибка 3. Перепутали индексацию¶

Ошибка 4. Хранят размер не только у корней¶

Ошибка 5. Используют DSU там, где нужны удаления¶

Что важно запомнить¶

Короткое резюме¶

1. `find(x)`¶

2. `same(a, b)`¶

3. `unite(a, b)`¶

Ошибка 1. Забыли вызвать `find` перед объединением¶