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>.
== Обобщение задачи для произвольных графов ==
написать про уровни и остовные леса <tex>\mathrm{navernoe.}</tex>
* [https://en.wikipedia.org/wiki/Dynamic_connectivity Dynamic connectivity {{---}} Википедия]
* [http://courses.csail.mit.edu/6.851/spring12/scribe/L20.pdf http://courses.csail.mit.edu/6.851/spring12/scribe/L20.pdf]
* [http://numeralis.ru/algoritmyi-i-strukturyi-dannyih-poiska-dinamicheskaya-svyaznost-v-grafah-babenko-maksim/ Лекции {{---}} Академия Яндекса]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Связность в графах]]
