693
правки
Изменения
Нет описания правки
Если задача такова, что в графе нет и не может быть циклов, то её можно решить при помощи [[Деревья Эйлерова обхода|деревьев эйлерова обхода]]. Нужно только... [[Dynamic connectivity|читать продолжение в источнике]].
Время работы каждого запроса для упрощённой задачи {{---}} <tex>O(\log n)</tex>.
== Обобщение задачи для произвольных графов ==
написать про уровни и остовные леса<tex>\mathrm{navernoe.}</tex>
<!-- === Псевдокод === xz -->
<!--== Алгоритм ==
=== Частные случаи ===
# Планарные графы. D. Eppstein доказал, что для планарных графов мы также можем выполнять запросы за <tex>O(\log n)</tex>.
-->
