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

Система непересекающихся множеств (СНМ, DSU) хранит разбиение элементов на группы и умеет:

• get(v) — вернуть представителя группы $v$;
• unite(a, b) — объединить группы $a$ и $b$.

Вопрос «лежат ли $a$ и $b$ в одной группе» — это get(a) == get(b).

Главный потребитель — алгоритм Краскала, но применений сильно больше.

Деревья

Каждую группу представим деревом. Хранить будем только родителя; представитель группы — корень.

Никакой связи с исходным графом у этого дерева нет — рёбра проводятся как удобно.

int get(int v) { return p[v] == v ? v : get(p[v]); }
void unite(int a, int b) {
    a = get(a); b = get(b);
    if (a != b) p[b] = a;
}

Просто, но медленно: подвешивая как попало, легко получить бамбук, и тогда get стоит линию.

Измерено: на цепочке из 200 000 вершин сто запросов get от нижнего конца дают 20 миллионов шагов.

Эвристика первая: сжатие путей

Найдя корень, переподвесим к нему все вершины на пройденном пути.

int get(int v) { return p[v] == v ? v : p[v] = get(p[v]); }

Одно присваивание. Следующий запрос по тем же вершинам пройдёт за один шаг.

Эвристика вторая: объединение по размеру

При объединении подвешиваем меньшее дерево к большему.

void unite(int a, int b) {
    a = get(a); b = get(b);
    if (a == b) return;
    if (size[a] < size[b]) swap(a, b);
    size[a] += size[b];
    p[b] = a;
}

Тогда, поднимаясь от вершины к корню, мы на каждом шаге переходим в поддерево хотя бы вдвое большего размера. Значит, шагов не больше $\log_2 n$ — и это гарантия, а не среднее.

Почему по размеру, а не по глубине

Естественно было бы подвешивать менее глубокое дерево к более глубокому. Так тоже делают — это «эвристика по рангу», — но рассуждение выше для глубин не проходит.

Причина: при подвешивании размер нового дерева — это в точности сумма размеров, а глубина так не выражается. Она может не измениться вовсе, и аргумент «поднимаясь, попадаем в вдвое большее» ломается.

С рангом (глубиной, посчитанной как если бы сжатия путей не было) оценка тоже верна, но доказывается сложнее. По размеру — проще и не хуже.

Обе вместе

Сжатие путей и объединение по размеру не мешают друг другу. Сжатие портит размеры промежуточных вершин — но они и не нужны: размер смотрят только у корня.

Вместе они дают амортизированную оценку $O(\alpha(n))$, где $\alpha$ — обратная функция Аккермана. Она растёт настолько медленно, что для любого $n$ меньше $10^{600}$ не превосходит четырёх.

Сколько это стоит на самом деле

Миллион случайных объединений на миллионе элементов:

реализация	шагов подъёма	время
сжатие путей + по размеру	1 343 136	27 мс
только объединение по размеру	1 812 801	29 мс
только сжатие путей	4 367 984	42 мс

Каждая эвристика по отдельности уже даёт приемлемый результат; вместе — лучший. Разница между «одна» и «обе» на случайных данных невелика, но на подобранных тестах первые две строки расходятся с третьей на порядок.

Реализация на одном массиве

Массив размеров можно не заводить. Договоримся: если p[v] отрицательно, то $v$ — корень, а $-p[v]$ — размер его дерева.

struct DSU {
    vector<int> p;
    DSU(int n) : p(n, -1) {}

    int get(int v) { return p[v] < 0 ? v : p[v] = get(p[v]); }

    bool unite(int a, int b) {
        a = get(a); b = get(b);
        if (a == b) return false;
        if (-p[a] < -p[b]) swap(a, b);      // a — большее дерево
        p[a] += p[b];
        p[b] = a;
        return true;
    }
};

Вдвое меньше памяти и одно обращение вместо двух. unite возвращает, произошло ли объединение, — ровно то, что нужно Краскалу.

Проверено: 30 000 сценариев по 20 операций — все четыре реализации (наивная, с одной эвристикой, с двумя) совпали с прямым поддержанием разбиения.

Рекурсия и стек

get рекурсивна, и на цепочке глубина рекурсии линейна. При $n = 10^6$ это переполнение стека до того, как сжатие путей успеет помочь.

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

int get(int v) {
    int root = v;
    while (p[root] >= 0) root = p[root];
    while (p[v] >= 0) { int next = p[v]; p[v] = root; v = next; }
    return root;
}

Два прохода вместо рекурсии, без вспомогательного массива.

Что ещё можно хранить

В корне удобно держать любую информацию о группе — размер, сумму, минимум, число рёбер. Обновляется она в unite за константу.

Так решают: «сколько компонент осталось», «какой размер компоненты вершины», «сколько рёбер внутри компоненты» (и, значит, есть ли в ней цикл).

Чего СНМ не умеет — разъединять. Все известные применения обходят это офлайном: обрабатывают запросы в обратном порядке, превращая удаления в добавления.