Задача о динамической связности — различия между версиями
(→Обобщение задачи для произвольных графов) |
|||
| Строка 27: | Строка 27: | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | Введём функцию l(e):e->{0..log n} и назовём её ``уровнем ребра``.<!--При выполнении операции add что-то хорошее, а с удалением не всё так просто.--> | ||
<!-- === Псевдокод === xz --> | <!-- === Псевдокод === xz --> | ||
<!--== Алгоритм == | <!--== Алгоритм == | ||
| Строка 33: | Строка 38: | ||
=== Деревья === //yes | === Деревья === //yes | ||
=== Планарные графы === //da xz... chtobi o nih govorit' ischo... --> | === Планарные графы === //da xz... chtobi o nih govorit' ischo... --> | ||
| − | |||
| − | |||
| − | |||
| − | |||
<!-- | <!-- | ||
== Алгоритм == | == Алгоритм == | ||
| − | |||
=== Решение упрощённой задачи === | === Решение упрощённой задачи === | ||
==== Задача без удалений рёбер ==== | ==== Задача без удалений рёбер ==== | ||
Версия 23:32, 7 января 2018
| Задача: |
Есть неориентированный граф из вершин, изначально не содержащий рёбер. Требуется обработать запросов трёх типов:
|
В этой статье будет приведено решение задачи online, то есть отвечать на get-запрос (проверять наличие пути между вершинами) мы будем сразу.
Содержание
Динамическая связность в лесах
Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в деревьях эйлерова обхода. Время работы каждого запроса для упрощённой задачи — .
Обобщение задачи для произвольных графов
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Но мы можем в каждой компоненте связности выделить остовные деревья, которые образуют остовный лес.
Введём функцию l(e):e->{0..log n} и назовём её ``уровнем ребра``.
