Задача о динамической связности — различия между версиями
| Строка 1: | Строка 1: | ||
{{Задача | {{Задача | ||
|definition = Есть [[Основные_определения:_граф,_ребро,_вершина,_степень,_петля,_путь,_цикл#Неориентированные_графы|неориентированный граф]] из <tex>n</tex> вершин, изначально не содержащий рёбер. Требуется обработать <tex>m</tex> запросов трёх типов: | |definition = Есть [[Основные_определения:_граф,_ребро,_вершина,_степень,_петля,_путь,_цикл#Неориентированные_графы|неориентированный граф]] из <tex>n</tex> вершин, изначально не содержащий рёбер. Требуется обработать <tex>m</tex> запросов трёх типов: | ||
| − | * <tex>\mathrm{add(u,v)}</tex> {{---}} добавить ребро между вершинами <tex>u</tex> и <tex>v</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{remove(u,v)}</tex> {{---}} удалить ребро между вершинами <tex>u</tex> и <tex>v</tex>; |
* <tex>\mathrm{connected(u,v)}</tex> {{---}} проверить, лежат ли вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связности. | * <tex>\mathrm{connected(u,v)}</tex> {{---}} проверить, лежат ли вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связности. | ||
}} | }} | ||
== Динамическая связность в лесах == | == Динамическая связность в лесах == | ||
| − | Если задача такова, что в графе нет и не может быть циклов, то | + | Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в [[Деревья Эйлерова обхода|деревьях эйлерова обхода]]. Время работы каждого запроса для упрощённой задачи {{---}} <tex>O(\log n)</tex>. |
| − | |||
| − | Время работы каждого запроса для упрощённой задачи {{---}} <tex>O(\log n)</tex>. | ||
== Обобщение задачи для произвольных графов == | == Обобщение задачи для произвольных графов == | ||
написать про уровни и остовные леса <tex>\mathrm{navernoe.}</tex> | написать про уровни и остовные леса <tex>\mathrm{navernoe.}</tex> | ||
| Строка 66: | Строка 64: | ||
* [https://en.wikipedia.org/wiki/Dynamic_connectivity Dynamic connectivity {{---}} Википедия] | * [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://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/ Лекции {{---}} Академия Яндекса] | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Связность в графах]] | [[Категория: Связность в графах]] | ||
Версия 21:08, 7 января 2018
| Задача: |
Есть неориентированный граф из вершин, изначально не содержащий рёбер. Требуется обработать запросов трёх типов:
|
Содержание
Динамическая связность в лесах
Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в деревьях эйлерова обхода. Время работы каждого запроса для упрощённой задачи — .
Обобщение задачи для произвольных графов
написать про уровни и остовные леса
