DSU: объединение множеств и сжатие пути

Каждый элемент в своём множестве — до объединения

Система непересекающихся множеств, или DSU (disjoint-set union, также union–find), хранит разбиение: каждый элемент принадлежит ровно одному непустому множеству, множества не пересекаются. Изначально каждый из n элементов образует отдельное множество. union(a, b) объединяет их множества целиком, а не только два отдельных элемента.

find(v) возвращает представителя множества. same(a, b) сравнивает представителей. Успешный union возвращает true и уменьшает число множеств на один; повторный — false. find и same могут менять родительские ссылки при сжатии, хотя принадлежность элементов множествам сохраняется.

Деревья родителей и представители

У каждого элемента есть родитель. Корень ссылается на себя; переходы по родителям всегда приводят к нему. Все элементы с одним корнем образуют множество. Корень — удобный представитель: он не обязан иметь наименьшую метку или совпадать с первым аргументом последнего union. При объединении он может измениться.

В плеере стрелка идёт от потомка к родителю, двойная окружность отмечает корень. Ссылки на себя на рисунке опущены, но видны в таблице parent. Это служебные ссылки DSU, а не рёбра исходного графа. По одной DSU нельзя восстановить маршрут между связанными вершинами графа.

Присоединяем меньшее множество к большему

Найдём оба корня. Если они совпали, множества уже объединены. Иначе сравним размеры и сделаем корень меньшего множества потомком корня большего. В оставшемся корне сложим размеры. При равных размерах побеждает корень первого аргумента: пример воспроизводится однозначно.

Размер имеет смысл только в корне. У бывшего корня в массиве остаётся устаревшее значение; при следующих объединениях оно не используется, а таблица показывает прочерк. Соединение корней сохраняет лес. Когда глубина элемента растёт при объединении по размеру, его множество как минимум удваивается: до сжатия глубина ограничена floor(log₂ n).

Находим корень и сокращаем путь

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

В исходном запуске union A B, union C D и union A C создают D → C → A. Вторая сбалансированная группа растёт под E; после union A E получаем H → G → E → A. Первый find H проходит три ссылки и меняет родителей H и G на A. Следующий find H проходит одну ссылку. В множестве по-прежнему все восемь элементов.

Что сохраняется после каждого изменения

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

Поэтому одинаковые представители означают одно множество, разные — разные множества. В исходном запуске same A E даёт false до последних объединений, а same D H после них — true. Затем union B H возвращает false: размер не прибавляется повторно, число множеств не уменьшается.

Связность, Краскал и ограничения

При добавлении рёбер неориентированного графа вызываем union для их концов. Проверка связности сводится к same. Краскал так отклоняет ребро, концы которого уже связаны; генерация лабиринта по Краскалу так же избегает цикла. Деревья DSU могут совсем не походить на выбранные рёбра графа.

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

Как читать и менять пример

Команды выполняются сверху вниз. Пишите find H, union A B и same D H, по одной на строке; регистр букв не важен. Выберите от 1 до 8 элементов (от A до H) и не более 32 команд. Пустые строки пропускаются, пустой список допустим. Применение начинает запуск с отдельных множеств; неверный ввод сохраняет текущий корректный запуск.

Таблица показывает родителя каждого элемента и размер, если элемент — корень. Текстовые группы дают состав множеств, поэтому состояние доступно и без чтения canvas. Счётчики учитывают завершённые команды, успешные объединения, переходы по родителям в первом проходе find и действительно изменённые сжатием ссылки. Чтение для отображения, сравнения корней, запись при объединении и присваивание прежнего родителя в сжатии не учитываются.

Общее управление даёт запуск/паузу, шаги, перемотку, скорость, полный экран и ссылку с восстановлением входа и шага на паузе в чистом плеере. Экспорт видео сохраняет лес, таблицу, счётчики и текущее действие без звука. Скорость анимации помогает объяснению, но не измеряет производительность.

Почти постоянная амортизированная стоимость

Инициализация занимает O(n) времени и памяти. С объединением по размеру и сжатием пути m команд find/union/same требуют суммарно O(n + m α(n)) времени, где α — очень медленно растущая обратная функция Аккермана. Это амортизированная оценка последовательности, а не обещание постоянного времени каждого find в худшем случае. Одна операция в худшем случае занимает O(log(n+1)); same и union делают не более двух find.

Итеративному алгоритму нужны O(n) для parent и size и O(1) дополнительной памяти на команду. Визуализация отдельно хранит неизменяемые снимки. Если создано S кадров, история занимает O(S(n+m)): каждый кадр копирует массивы и накопленные ответы. Определение корней для кадра требует O(n log(n+1)); ограничения редактора сдерживают эти расходы. Они не входят в оценку самой DSU.

Реализация на JavaScript

Самостоятельная реализация использует те же два прохода сжатия, объединение по размеру и порядок при равенстве, что плеер, без истории анимации. Элементы нумеруются от 0 до n−1. Оба аргумента проверяются до бинарной команды: неверный второй аргумент не должен частично сжать путь первого. В прикладном коде храните parent и size как внутреннее состояние.

class DSU {
    constructor(n) {
        if (!Number.isInteger(n) || n < 1)
            throw new RangeError("Expected a positive element count");
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.size = Array(n).fill(1);
        this.components = n;
    }
    check(v) {
        if (!Number.isInteger(v) || v < 0 || v >= this.parent.length)
            throw new RangeError("Invalid element");
    }
    find(v) {
        this.check(v);
        let root = v;
        while (this.parent[root] !== root) root = this.parent[root];
        // Second pass: every visited element points straight to the root.
        while (v !== root) {
            const next = this.parent[v];
            this.parent[v] = root;
            v = next;
        }
        return root;
    }
    union(a, b) {
        this.check(a); this.check(b);
        a = this.find(a); b = this.find(b);
        if (a === b) return false;
        if (this.size[a] < this.size[b]) [a, b] = [b, a];
        this.parent[b] = a;
        this.size[a] += this.size[b];
        this.components--;
        return true;
    }
    same(a, b) {
        this.check(a); this.check(b);
        return this.find(a) === this.find(b);
    }
}

const dsu = new DSU(4); // A=0, B=1, C=2, D=3
dsu.union(0, 1);
dsu.union(2, 3);
dsu.union(0, 2);        // D → C → A
dsu.find(3);           // 0; now D → A
dsu.same(1, 3);        // true
dsu.union(1, 3);       // false: already in the same set