Задача о динамической связности — различия между версиями
| Строка 26: | Строка 26: | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
<!-- === Псевдокод === xz --> | <!-- === Псевдокод === xz --> | ||
| Строка 45: | Строка 34: | ||
=== Планарные графы === //da xz... chtobi o nih govorit' ischo... --> | === Планарные графы === //da xz... chtobi o nih govorit' ischo... --> | ||
| − | + | ||
| + | |||
| + | |||
<!-- | <!-- | ||
== Алгоритм == | == Алгоритм == | ||
Версия 23:20, 7 января 2018
| Задача: |
Есть неориентированный граф из вершин, изначально не содержащий рёбер. Требуется обработать запросов трёх типов:
|
В этой статье будет приведено решение задачи online, то есть отвечать на get-запрос (проверять наличие пути между вершинами) мы будем сразу.
Содержание
Динамическая связность в лесах
Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в деревьях эйлерова обхода. Время работы каждого запроса для упрощённой задачи — .
Обобщение задачи для произвольных графов
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Но мы можем в каждой компоненте связности выделить остовные деревья, которые образуют остовный лес.
