Изменения
Нет описания правки
{{Задача
|definition = Имеется Есть [[Основные_определения:_граф,_ребро,_вершина,_степень,_петля,_путь,_цикл#Неориентированные_графы|неориентированный граф]] из <tex>n</tex> вершин, изначально не содержащий рёбер. Требуется обработать <tex>m</tex> запросов трёх типов:
* добавить ребро между вершинами <tex>u</tex> и <tex>v</tex>,
* удалить ребро между вершинами <tex>u</tex> и <tex>v</tex>,
* проверить, лежат ли вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связности.
}}
== Алгоритм ==
Вместо описанного способа откатывания состояния СНМ можно использовать [[Персистентные структуры данных|персистентный]] СНМ, но этот вариант сложнее и имеет меньшую эффективность. <!-- Я не уверен, бывает ли персистентный СНМ, работающий за log. -->
== Время работы Частные случаи == # Деревья. Для таких графов задачу можно решать при помощи [[Деревья Эйлерова обхода|деревьев эйлерова обхода]]. Операции добавления и удаления рёбер и проверка на существование пути между вершинами работают за <tex>O(\log n)</tex>. # Планарные графы. D. Eppstein доказал, что для планарных графов мы также можем выполнять запросы за <tex>O(\log n)</tex>.<ref>David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert Endre Tarjan, Jeffery Westbrook,Moti Yung: Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph.J. Algorithms 13(1): 33-54 (1992)</ref>
== См. также ==
