Непересекающиеся множества: компоненты и объединения

В сети постепенно появляются связи между узлами. После каждой новой связи спрашивают: соединены ли A и B каким-нибудь путём? Повторный BFS для каждого вопроса просмотрит большую часть графа. Если связи только добавляются, можно хранить компоненты напрямую.

Представитель компоненты

Disjoint Set Union, или union-find, поддерживает непересекающиеся множества. Find возвращает представителя компоненты, Union объединяет две компоненты. Представитель — техническое значение, а не самый маленький ID и не главный узел сети.

Сначала каждый из n элементов образует отдельное множество: parent[i]=i. Связь parent описывает дерево представителей. Корень ссылается на себя. Два элемента в одной компоненте тогда и только тогда, когда Find возвращает одинаковые корни.

func Find(parent []int, x int) int {
    for parent[x] != x {
        parent[x] = parent[parent[x]]
        x = parent[x]
    }
    return x
}

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

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

После Find(a) иFind(b) не меняйте структуру, если корни равны. Иначе присоедините меньшее дерево к большему и обновите размер только нового корня. Размер некорневого элемента не обязан обозначать размер всей компоненты; обращайтесь к size[Find(x)].

Почему это полезно? Без сжатия пути глубина элемента может увеличиться при присоединении его меньшей компоненты к большей. При таком увеличении размер компоненты хотя бы удваивается. Следовательно, глубина не больше O(log n). Вместе со сжатием пути серия операций получает амортизированную оценку O(α(n)), где α — обратная функция Аккермана, очень медленно растущая. Называть каждую операцию строго O(1) не нужно: договор оценки точнее.

Компонента не хранит маршрут

На связях 0−1 и 1−2 Find(0)==Find(2). Но DSU не помнит, через какие рёбра проходит путь. Дерево parent — структура реализации и может содержать связь 0→2, которой в исходной сети нет. Для восстановления маршрута нужен сам граф и поиск пути.

Удаление связи — другая задача. После удаления 1−2 нельзя просто отделить один узел parent: сжатие пути уже изменило технические связи, а альтернативные пути могут сохранять компоненту. Базовый DSU не поддерживает произвольное удаление. Для динамической связности используют дополнительные методы с иным договором.

Применение к циклам и остовам

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

Алгоритм Краскала сортирует неориентированные взвешенные рёбра по весу и добавляет только соединяющие разные компоненты. Получается минимальный остов для связного графа, либо минимальный остовный лес для несвязного. Это дополнительная задача: не путайте остов с кратчайшими путями от источника. Остов минимизирует сумму выбранных рёбер, а Дейкстра — расстояния до вершин.

Самостоятельная лаборатория

Создайте DSU с методами New(n),Find(x),Union(a,b),Connected(a,b). Определите обработку неправильных индексов: ошибка, а не скрытая паника. Union должен сообщать, изменилось ли число компонент. Проверьте объединения 0−1,1−2, затем повтор 0−2: третье не должно уменьшить счётчик.

Для маленькой сети после каждого случайного добавления ребра сравните Connected со свежим BFS по сохранённому графу. Этот тест проверяет внешний смысл структуры, а не конкретные значения parent. Практика — 60 минут.

Критерии готовности: корень ссылается на себя; размер обновлён только при реальном объединении; Connected не зависит от выбранного представителя; явно запрещены удаления; направленный цикл не подменён неориентированной связностью.

Разбор

На пяти изначально независимых узлах число компонент 5. После 0−1 и 1−2 оно 3; повтор 0−2 оставляет 3. Проверка parent[0]==parent[2] безFind может дать неверный ответ в корректной структуре до полного сжатия путей.

Источники: Princeton: union-find, minimum spanning trees. Обе темы имеют открытые авторские материалы, но их готовые задания здесь не копируются.