Задача о динамической связности
| Задача: |
Есть неориентированный граф из вершин, изначально не содержащий рёбер. Требуется обработать запросов трёх типов:
|
Содержание
Алгоритм
Решение упрощённой задачи
Задача без удалений рёбер
Если нет удалений рёбер, задачу можно решить при помощи системы непересекающихся множеств. Каждая компонента связности — одно множество в СНМ, и при добавлении рёбер они объединяются.
Время работы такого решения: , где — обратная функция Аккермана.
Построение дерева отрезков
Рассмотрим массив запросов. Каждое ребро в графе существует на некотором отрезке запросов: начиная с запроса добавления и заканчивая запросом удаления (либо концом запросов, если ребро не было удалено). Для каждого ребра можно найти этот отрезок, пройдя по массиву запросов и запоминая, когда какое ребро было добавлено.
Пусть есть рёбер, -е соединяет вершины и , было добавлено запросом и удалено запросом .
Построим на массиве запросов дерево отрезков, в каждой его вершине будем хранить список пар. -е рёбро графа нужно добавить на отрезок . Это делается аналогично тому, как в дереве отрезков происходит добавление на отрезке (процесс описан в статье "Несогласованные поддеревья. Реализация массового обновления"), но без : нужно спуститься по дереву от корня и записать пару в вершины дерева отрезков.
Теперь чтобы узнать, какие рёбра существуют во время выполнения -го запроса, достаточно посмотреть на путь от корня дерева отрезков до листа, который соответствует этому запросу — рёбра, записанные в вершинах этого пути, существуют во время выполнения запроса.
Ответы на запросы
Обойдём дерево отрезков в глубину, начиная с корня. Будем поддерживать граф, состоящий из рёбер, которые содержатся на пути от текущей вершины дерева отрезков до корня. При входе в вершину добавим в граф рёбра, записанные в этой вершине. При выходе из вершины нужно откатить граф к состоянию, которое было при входе. Когда мы добираемся до листа, в граф уже добавлены все рёбра, которые существуют во время выполнения соответствующего запроса, и только они. Поэтому если этот лист соответствует запросу третьего типа, его следует выполнить и сохранить ответ.
Для поддержания такого графа и ответа на запросы будем использовать систему непересекающихся множеств. При добавлении рёбер в граф объединим соответствующие множества в СНМ. Откатывание состояния СНМ описано ниже.
СНМ с откатами
Для того, чтобы иметь возможность откатывать состояние СНМ, нужно при каждом изменении любого значения в СНМ записывать в специальный массив, что именно изменилось и какое было предыдущее значение. Это можно реализовать как массив пар (указатель, значение).
Чтобы откатить состояние СНМ, пройдём по этому массиву в обратном порядке и присвоим старые значения обратно. Для лучшего понимания ознакомьтесь с приведённой ниже реализацией.
Нужно заметить, что эвристику сжатия путей в этом случае применять не следует. Эта эвристика улучшает асимптотическое время работы, но это время работы не истинное, а амортизированное. Из-за наличия откатов к предыдущим состояниям эта эвристика не даст выигрыша. СНМ с ранговой эвристикой же работает за на запрос истинно.
Запоминание изменений и откаты не влияют на время работы, если оно истинное, а не амортизированное. Действительно: пусть в СНМ произошло изменений. Каждое из них будет один раз занесено в массив и один раз отменено. Значит, запись в массив и откаты работают за . Но и сами изменения заняли времени, значит, откаты не увеличили асимптотическое время работы.
Вместо описанного способа откатывания состояния СНМ можно использовать персистентный СНМ, но этот вариант сложнее и имеет меньшую эффективность.
Частные случаи
- Деревья. Для таких графов задачу можно решать при помощи деревьев эйлерова обхода. Операции добавления и удаления рёбер и проверка на существование пути между вершинами работают за .
- Планарные графы. D. Eppstein доказал, что для планарных графов мы также можем выполнять запросы за .
