Задача о динамической связности — различия между версиями
(→Обобщение задачи для произвольных графов) |
|||
| Строка 10: | Строка 10: | ||
Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в [[Деревья Эйлерова обхода|деревьях эйлерова обхода]]. Время работы каждого запроса для упрощённой задачи {{---}} <tex>O(\log n)</tex>. | Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в [[Деревья Эйлерова обхода|деревьях эйлерова обхода]]. Время работы каждого запроса для упрощённой задачи {{---}} <tex>O(\log n)</tex>. | ||
== Обобщение задачи для произвольных графов == | == Обобщение задачи для произвольных графов == | ||
| − | + | ||
| + | Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Но мы можем в каждой компоненте связности выделить [[https://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%81%D1%82%D0%BE%D0%B2%D0%BD%D1%8B%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D1%8C%D1%8F:_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F,_%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D0%B1%D0%B5%D0%B7%D0%BE%D0%BF%D0%B0%D1%81%D0%BD%D0%BE%D0%BC_%D1%80%D0%B5%D0%B1%D1%80%D0%B5|остовные деревья]], которые образуют остовный лес. | ||
| + | |||
| + | |||
| + | |||
| + | <!--Рассмотрим возможные случаи изменения графа с точки зрения связности после выполнения update-запросов.--> | ||
| + | |||
| + | <!--После операции добавления могло возникнуть следующее: | ||
| + | * вершины у и в лежали в одной компоненте связности, значение коннектед() до и после запроса не изменилось ни для какой пары вершин | ||
| + | * вершины лежали в разных компонентах, теперь новое ребро их соединило 12321232123212321232123212321 | ||
| + | |||
| + | После операции удаления: | ||
| + | * если удаляемое ребро - мост, то компонента связности распалась на две | ||
| + | * иначе значение коннектед() осталось прежним для любой пары вершин | ||
| + | |||
| + | чё это значит? смотрим видосик!!!--> | ||
| + | |||
<!-- === Псевдокод === xz --> | <!-- === Псевдокод === xz --> | ||
<!--== Алгоритм == | <!--== Алгоритм == | ||
| Строка 16: | Строка 32: | ||
== Частные случаи == // hahaha there is only one specific kind))0) | == Частные случаи == // hahaha there is only one specific kind))0) | ||
=== Деревья === //yes | === Деревья === //yes | ||
| − | === Планарные графы === //da xz chtobi o nih govorit' ischo... --> | + | === Планарные графы === //da xz... chtobi o nih govorit' ischo... --> |
| + | |||
== == | == == | ||
<!-- | <!-- | ||
Версия 22:24, 7 января 2018
| Задача: |
Есть неориентированный граф из вершин, изначально не содержащий рёбер. Требуется обработать запросов трёх типов:
|
В этой статье будет приведено решение задачи online, то есть отвечать на get-запрос (проверять наличие пути между вершинами) мы будем сразу.
Содержание
Динамическая связность в лесах
Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в деревьях эйлерова обхода. Время работы каждого запроса для упрощённой задачи — .
Обобщение задачи для произвольных графов
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Но мы можем в каждой компоненте связности выделить [деревья], которые образуют остовный лес.
