693
правки
Изменения
Нет описания правки
{{Задача
|definition = Есть [[Основные_определения:_граф,_ребро,_вершина,_степень,_петля,_путь,_цикл#Неориентированные_графы|неориентированный граф]] из <tex>n</tex> вершин, изначально не содержащий рёбер. Требуется обработать <tex>m</tex> запросов трёх типов:
* <tex>\mathrm{add(u,v)}</tex> {{---}} добавить ребро между вершинами <tex>u</tex> и <tex>v</tex>,* <tex>\mathrm{remove(u,v)}</tex> {{---}} удалить ребро между вершинами <tex>u</tex> и <tex>v</tex>,* <tex>\mathrm{connected(u,v)}</tex> {{---}} проверить, лежат ли вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связности.
}}
== Динамическая связность в лесах ==
Если задача построена тактакова, что в графе нет и не может быть циклов, то её можно решить при помощи [[Деревья Эйлерова обхода|деревьев эйлерова обхода]]. Нужно только... [[Dynamic connectivity|читать продолжение в источнике]].
Время работы для упрощённой задачи {{---}} <tex>O(\log n)</tex>.
== Обобщение задачи о динамической связности для произвольных графов ==А это уже сложнее)0)написать про уровни и остовные леса<!-- === Псевдокод ===xz -->
<!--== Алгоритм ==
=== Время работы === // i think i'll tell it
