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