Задача о динамической связности — различия между версиями
(→Обобщение задачи для произвольных графов) |
(→Обобщение задачи для произвольных графов) |
||
Строка 41: | Строка 41: | ||
* '''Удаляемое ребро не является мостом'''. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины <tex>u</tex> и <tex>v</tex> лежат в разных частях. Если <tex>uv</tex> принадлежало нашему лесу, то передаём эту "функцию" новому ребру. | * '''Удаляемое ребро не является мостом'''. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины <tex>u</tex> и <tex>v</tex> лежат в разных частях. Если <tex>uv</tex> принадлежало нашему лесу, то передаём эту "функцию" новому ребру. | ||
− | Осталось проверить, является ли ребро мостом. Будем искать ребро <tex>xy</tex> на уровне <tex>l(xy) \ leqslant l(uv)</tex>. Рассматривать будем меньшую из частей (будем считать, что <tex>|T(u)|\leqslant|T(v)|</tex>, в противном случае просто поменяем исследуемые вершины местами). Если мы находим такое ребро, что оно ведёт в другую часть, то останавливаемся и говорим, что <tex>uv</tex> не мост. Иначе увеличиваем уровень ребра, чтобы заново к нему не обращаться. Суммарная сложность сканирования рёбер будет <tex>O(|T(u)|\mathrm{\log}n)</tex>, так как мы проверяем каждую вершину из <tex>T(u)</tex>, а уровень ребра не превосходит <tex>\mathrm{\log}n</tex>. | + | Осталось проверить, является ли ребро мостом. Будем искать ребро <tex>xy</tex> на уровне <tex>l(xy) \ leqslant l(uv)</tex>. Рассматривать будем меньшую из частей (будем считать, что <tex>|T(u)|\leqslant|T(v)|</tex>, в противном случае просто поменяем исследуемые вершины местами). Если мы находим такое ребро, что оно ведёт в другую часть, то останавливаемся и говорим, что <tex>uv</tex> не мост. Иначе увеличиваем уровень ребра, чтобы заново к нему не обращаться. Суммарная сложность сканирования рёбер будет <tex>O(|T(u)|\mathrm{\log}n)</tex>, так как в худшем случае мы проверяем каждую вершину из <tex>T(u)</tex>, а уровень ребра не превосходит <tex>\mathrm{\log}n</tex>. |
Версия 01:10, 8 января 2018
Задача: |
Есть неориентированный граф из вершин, изначально не содержащий рёбер. Требуется обработать запросов трёх типов:
|
В этой статье будет приведено решение задачи online, то есть отвечать на get-запрос (проверять наличие пути между вершинами) мы будем сразу.
Содержание
Динамическая связность в лесах
Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в деревьях эйлерова обхода. Время работы каждого запроса для упрощённой задачи — .
Обобщение задачи для произвольных графов
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Добавление рёбер можно рассмотреть с точки зрения системы непересекающихся множеств, такой запрос будет работать за
.Попробуем выполнить операцию удаления ребра. Для этого в каждой компоненте связности выделим остовные деревья, которые образуют остовный лес. Граф и его остовный лес — одно и то же с точки зрения связности.
Введём функцию
и назовём её уровнем ребра . Будем рассматривать графы . Очевидно, что . Выделим в них остовные леса таким образом, чтобы , где — остовный лес графа .При удалении возможны случаи:
- Удаляемое ребро является мостом. В этом случае дерево распадается на две части (назовём их и ), и задача решается как для дерева за .
- Удаляемое ребро не является мостом. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины и лежат в разных частях. Если принадлежало нашему лесу, то передаём эту "функцию" новому ребру.
Осталось проверить, является ли ребро мостом. Будем искать ребро
на уровне . Рассматривать будем меньшую из частей (будем считать, что , в противном случае просто поменяем исследуемые вершины местами). Если мы находим такое ребро, что оно ведёт в другую часть, то останавливаемся и говорим, что не мост. Иначе увеличиваем уровень ребра, чтобы заново к нему не обращаться. Суммарная сложность сканирования рёбер будет , так как в худшем случае мы проверяем каждую вершину из , а уровень ребра не превосходит .