Задача о динамической связности
| Задача: |
Есть неориентированный граф из вершин, изначально не содержащий рёбер. Требуется обработать запросов трёх типов:
|
В этой статье будет приведено решение задачи online, то есть отвечать на get-запрос (проверять наличие пути между вершинами) мы будем сразу.
Динамическая связность в лесах
Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в деревьях эйлерова обхода. Время работы каждого запроса для упрощённой задачи — .
Обобщение задачи для произвольных графов
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Добавление рёбер можно рассмотреть с точки зрения системы непересекающихся множеств, такой запрос будет работать за .
Попробуем выполнить операцию удаления ребра. Для этого в каждой компоненте связности выделим остовные деревья, которые образуют остовный лес. Граф и его остовный лес — одно и то же с точки зрения связности.
Введём функцию и назовём её уровнем ребра . Будем рассматривать графы . Очевидно, что . Выделим в них остовные леса таким образом, чтобы , где — остовный лес графа .
При удалении возможны случаи:
- Удаляемое ребро является мостом. В этом случае дерево распадается на две части, и задача решается как для дерева за .
- Удаляемое ребро не является мостом. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины и лежат в разных частях. Если принадлежало нашему лесу, то передаём эту "функцию" новому ребру.
Осталось проверить, является ли ребро мостом. Будем искать ребро на уровне .
