Изменения

Вместо описанного способа откатывания состояния СНМ можно использовать [[Персистентные структуры данных|персистентный]] СНМ, но этот вариант сложнее и имеет меньшую эффективность.

=== Частные случаи ===

# Деревья. Для таких графов задачу можно решать при помощи [[Деревья Эйлерова обхода|деревьев эйлерова обхода]]. Операции добавления и удаления рёбер и проверка на существование пути между вершинами работают за <tex>O(\log n)</tex>.

# Планарные графы. D. Eppstein доказал, что для планарных графов мы также можем выполнять запросы за <tex>O(\log n)</tex>.

== См. также ==