Задача о динамической связности — различия между версиями
(→См. также) |
|||
| Строка 6: | Строка 6: | ||
}} | }} | ||
| + | == Динамическая связность в лесах == | ||
| + | Если задача построена так, что в графе нет и не может быть циклов, то её можно решить при помощи [[Деревья Эйлерова обхода|деревьев эйлерова обхода]]. Нужно только... [[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... --> | ||
| + | |||
| + | <!-- | ||
== Алгоритм == | == Алгоритм == | ||
| Строка 38: | Строка 52: | ||
Вместо описанного способа откатывания состояния СНМ можно использовать [[Персистентные структуры данных|персистентный]] СНМ, но этот вариант сложнее и имеет меньшую эффективность. | Вместо описанного способа откатывания состояния СНМ можно использовать [[Персистентные структуры данных|персистентный]] СНМ, но этот вариант сложнее и имеет меньшую эффективность. | ||
| − | <! | + | <!- если бы ещё псевдокод и что-то там ещё, я забыла -> |
=== Частные случаи === | === Частные случаи === | ||
| Строка 44: | Строка 58: | ||
# Деревья. Для таких графов задачу можно решать при помощи [[Деревья Эйлерова обхода|деревьев эйлерова обхода]]. Операции добавления и удаления рёбер и проверка на существование пути между вершинами работают за <tex>O(\log n)</tex>. | # Деревья. Для таких графов задачу можно решать при помощи [[Деревья Эйлерова обхода|деревьев эйлерова обхода]]. Операции добавления и удаления рёбер и проверка на существование пути между вершинами работают за <tex>O(\log n)</tex>. | ||
# Планарные графы. D. Eppstein доказал, что для планарных графов мы также можем выполнять запросы за <tex>O(\log n)</tex>. | # Планарные графы. D. Eppstein доказал, что для планарных графов мы также можем выполнять запросы за <tex>O(\log n)</tex>. | ||
| + | --> | ||
== См. также == | == См. также == | ||
| − | * [[ | + | * [[Деревья Эйлерова обхода|Деревья эйлерова обхода]] |
* [[Задача о динамической связности оффлайн]] | * [[Задача о динамической связности оффлайн]] | ||
Версия 18:10, 7 января 2018
| Задача: |
Есть неориентированный граф из вершин, изначально не содержащий рёбер. Требуется обработать запросов трёх типов:
|
Содержание
Динамическая связность в лесах
Если задача построена так, что в графе нет и не может быть циклов, то её можно решить при помощи деревьев эйлерова обхода. Нужно только... читать продолжение в источнике.
Время работы для упрощённой задачи — .
Обобщение задачи о динамической связности
А это уже сложнее)0)
