693
правки
Изменения
Нет описания правки
}}
== Динамическая связность в лесах ==
Если задача построена так, что в графе нет и не может быть циклов, то её можно решить при помощи [[Деревья Эйлерова обхода|деревьев эйлерова обхода]]. Нужно только... [[Dynamic connectivity|читать продолжение в источнике]].
Время работы для упрощённой задачи {{---}} <tex>O(\log n)</tex>.
== Обобщение задачи о динамической связности ==
А это уже сложнее)0)
=== Псевдокод ===
<!--== Алгоритм ==
=== Время работы === // i think i'll tell it
== Частные случаи == // hahaha there is only one specific kind))0)
=== Деревья === //yes
=== Планарные графы === //da xz chtobi o nih govorit' ischo... -->
<!--
== Алгоритм ==
Вместо описанного способа откатывания состояния СНМ можно использовать [[Персистентные структуры данных|персистентный]] СНМ, но этот вариант сложнее и имеет меньшую эффективность.
<!-- если бы ещё псевдокод и что-то там ещё, я забыла -->
=== Частные случаи ===
# Деревья. Для таких графов задачу можно решать при помощи [[Деревья Эйлерова обхода|деревьев эйлерова обхода]]. Операции добавления и удаления рёбер и проверка на существование пути между вершинами работают за <tex>O(\log n)</tex>.
# Планарные графы. D. Eppstein доказал, что для планарных графов мы также можем выполнять запросы за <tex>O(\log n)</tex>.
-->
== См. также ==
* [[СНМ (реализация с помощью леса корневых деревьев)Деревья Эйлерова обхода|Система непересекающихся множествДеревья эйлерова обхода]]
* [[Задача о динамической связности оффлайн]]
