|
|
| Строка 44: |
Строка 44: |
| | | | |
| | Общее время удаления одного ребра не превосходит <tex>O(\mathrm{\log}^2{n}+S*\mathrm{\log}n)</tex>, где <tex>S</tex> {{---}} число неудачных сканирований, а для всех <tex>m</tex> запросов получаем <tex>O(\mathrm{\log}^2{n}*m+\mathrm{\log}n*\sum{S}) \leqslant O(\mathrm{\log}^2{n}*m+\mathrm{\log}n*\mathrm{\log}n*m) = O(2*\mathrm{\log}^2{n}*m)</tex>, поэтому для одного запроса будем иметь время <tex>O(\mathrm{\log}^2{n})</tex>. | | Общее время удаления одного ребра не превосходит <tex>O(\mathrm{\log}^2{n}+S*\mathrm{\log}n)</tex>, где <tex>S</tex> {{---}} число неудачных сканирований, а для всех <tex>m</tex> запросов получаем <tex>O(\mathrm{\log}^2{n}*m+\mathrm{\log}n*\sum{S}) \leqslant O(\mathrm{\log}^2{n}*m+\mathrm{\log}n*\mathrm{\log}n*m) = O(2*\mathrm{\log}^2{n}*m)</tex>, поэтому для одного запроса будем иметь время <tex>O(\mathrm{\log}^2{n})</tex>. |
| − |
| |
| − |
| |
| − | <!-- я лошара) -->
| |
| − | <!--== Алгоритм ==
| |
| − | === Время работы === // i think i'll tell it
| |
| − | == Частные случаи == // hahaha there is only one specific kind))0)
| |
| − | === Деревья === //yes
| |
| − | === Планарные графы === //da xz... chtobi o nih govorit' ischo... -->
| |
| − | <!--
| |
| − | == Алгоритм ==
| |
| − | === Решение упрощённой задачи ===
| |
| − | ==== Задача без удалений рёбер ====
| |
| − | Если нет удалений рёбер, задачу можно решить при помощи [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]]. Каждая компонента связности {{---}} одно множество в СНМ, и при добавлении рёбер они объединяются.
| |
| − |
| |
| − | Время работы такого решения: <tex>O(m \cdot \alpha (n))</tex>, где <tex>\alpha</tex> {{---}} [[СНМ (реализация с помощью леса корневых деревьев)#Функция Аккермана|обратная функция Аккермана]].
| |
| − |
| |
| − | === Построение дерева отрезков ===
| |
| − | Рассмотрим массив запросов. Каждое ребро в графе существует на некотором отрезке запросов: начиная с запроса добавления и заканчивая запросом удаления (либо концом запросов, если ребро не было удалено). Для каждого ребра можно найти этот отрезок, пройдя по массиву запросов и запоминая, когда какое ребро было добавлено.
| |
| − |
| |
| − | Пусть есть <tex>k</tex> рёбер, <tex>i</tex>-е соединяет вершины <tex>v_i</tex> и <tex>u_i</tex>, было добавлено запросом <tex>L_i</tex> и удалено запросом <tex>R_i</tex>.
| |
| − |
| |
| − | Построим на массиве запросов [[Дерево отрезков. Построение|дерево отрезков]], в каждой его вершине будем хранить список пар. <tex>i</tex>-е рёбро графа нужно добавить на отрезок <tex>[L_i,R_i]</tex>. Это делается аналогично тому, как в дереве отрезков происходит добавление на отрезке (процесс описан в статье "[[Несогласованные поддеревья. Реализация массового обновления]]"), но без <tex>push</tex>: нужно спуститься по дереву от корня и записать пару <tex>u_i,v_i</tex> в вершины дерева отрезков.
| |
| − |
| |
| − | Теперь чтобы узнать, какие рёбра существуют во время выполнения <tex>i</tex>-го запроса, достаточно посмотреть на путь от корня дерева отрезков до листа, который соответствует этому запросу {{---}} рёбра, записанные в вершинах этого пути, существуют во время выполнения запроса.
| |
| − |
| |
| − | === Ответы на запросы ===
| |
| − | Обойдём дерево отрезков в глубину, начиная с корня. Будем поддерживать граф, состоящий из рёбер, которые содержатся на пути от текущей вершины дерева отрезков до корня. При входе в вершину добавим в граф рёбра, записанные в этой вершине. При выходе из вершины нужно откатить граф к состоянию, которое было при входе. Когда мы добираемся до листа, в граф уже добавлены все рёбра, которые существуют во время выполнения соответствующего запроса, и только они. Поэтому если этот лист соответствует запросу третьего типа, его следует выполнить и сохранить ответ.
| |
| − |
| |
| − | Для поддержания такого графа и ответа на запросы будем использовать [[СНМ (реализация с помощью леса корневых деревьев)|систему непересекающихся множеств]]. При добавлении рёбер в граф объединим соответствующие множества в СНМ. Откатывание состояния СНМ описано ниже.
| |
| − |
| |
| − | === СНМ с откатами ===
| |
| − | Для того, чтобы иметь возможность откатывать состояние СНМ, нужно при каждом изменении любого значения в СНМ записывать в специальный массив, что именно изменилось и какое было предыдущее значение. Это можно реализовать как массив пар (указатель, значение).
| |
| − |
| |
| − | Чтобы откатить состояние СНМ, пройдём по этому массиву в обратном порядке и присвоим старые значения обратно. Для лучшего понимания ознакомьтесь с приведённой ниже реализацией.
| |
| − |
| |
| − | Нужно заметить, что эвристику сжатия путей в этом случае применять не следует. Эта эвристика улучшает асимптотическое время работы, но это время работы не истинное, а амортизированное. Из-за наличия откатов к предыдущим состояниям эта эвристика не даст выигрыша. СНМ с ранговой эвристикой же работает за <tex>O(\log n)</tex> на запрос истинно.
| |
| − |
| |
| − | Запоминание изменений и откаты не влияют на время работы, если оно истинное, а не амортизированное. Действительно: пусть в СНМ произошло <tex>r</tex> изменений. Каждое из них будет один раз занесено в массив и один раз отменено. Значит, запись в массив и откаты работают за <tex>\Theta(r)</tex>. Но и сами изменения заняли <tex>\Theta(r)</tex> времени, значит, откаты не увеличили асимптотическое время работы.
| |
| − |
| |
| − | Вместо описанного способа откатывания состояния СНМ можно использовать [[Персистентные структуры данных|персистентный]] СНМ, но этот вариант сложнее и имеет меньшую эффективность.
| |
| − | <!- если бы ещё псевдокод и что-то там ещё, я забыла ->
| |
| − |
| |
| − | === Частные случаи ===
| |
| − | # Планарные графы. D. Eppstein доказал, что для планарных графов мы также можем выполнять запросы за <tex>O(\log n)</tex>.
| |
| − | -->
| |
| | | | |
| | == См. также == | | == См. также == |
| Задача: |
Есть неориентированный граф из [math]n[/math] вершин, изначально не содержащий рёбер. Требуется обработать [math]m[/math] запросов трёх типов:
- [math]\mathrm{add(u,v)}[/math] — добавить ребро между вершинами [math]u[/math] и [math]v[/math];
- [math]\mathrm{remove(u,v)}[/math] — удалить ребро между вершинами [math]u[/math] и [math]v[/math];
- [math]\mathrm{connected(u,v)}[/math] — проверить, лежат ли вершины [math]u[/math] и [math]v[/math] в одной компоненте связности.
|
В этой статье будет приведено решение задачи online, то есть отвечать на get-запрос (проверять наличие пути между вершинами) мы будем сразу.
Динамическая связность в лесах
Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в деревьях эйлерова обхода. Время работы каждого запроса для упрощённой задачи — [math]O(\log n)[/math].
Обобщение задачи для произвольных графов
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Добавление рёбер можно рассмотреть с точки зрения системы непересекающихся множеств, такой запрос будет работать за [math]O(\mathrm{\log}n)[/math]. Операция проверки сводится к проверке связности в остовном лесе и работает также за [math]O(\mathrm{\log}n)[/math].
Попробуем выполнить операцию удаления ребра. Для этого в каждой компоненте связности выделим остовные деревья, которые образуют остовный лес. Граф и его остовный лес — одно и то же с точки зрения связности.
Введём функцию [math]l(e):e{\rightarrow}[0;\mathrm{\log} n][/math] и назовём её уровнем ребра [math]e[/math]. Будем рассматривать графы [math]G_i=\langle V, E\rangle: \{E | l(E) \geqslant i\}[/math]. Очевидно, что [math]G_{\mathrm{\log}n} \subseteq G_{\mathrm{\log}n-1} \subseteq ... \subseteq G_1 \subseteq G_0[/math]. Выделим в них остовные леса таким образом, что [math]F_{\mathrm{\log}n} \subseteq F_{\mathrm{\log}n-1} \subseteq ... \subseteq F_1 \subseteq F_0[/math], где [math]F_i[/math] — остовный лес графа [math]G_i[/math].
При удалении возможны случаи:
- Удаляемое ребро является мостом. В этом случае дерево распадается на две части (назовём их [math]T(u)[/math] и [math]T(v)[/math]), и задача решается как для дерева за [math]O(\mathrm{\log}n)[/math].
- Удаляемое ребро не является мостом. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины [math]u[/math] и [math]v[/math] лежат в разных частях. Если [math]uv[/math] принадлежало нашему лесу, то передаём эту "функцию" новому ребру.
Осталось проверить, является ли ребро мостом. Будем искать ребро [math]xy[/math] на уровне [math]l(uv)[/math], затем [math]l(uv)-1[/math], [math]l(uv)-2[/math][math]{{...}}[/math]. Рассматривать будем меньшую из частей (будем считать, что [math]|T(u)|\leqslant|T(v)|[/math], в противном случае просто поменяем исследуемые вершины местами). Если мы находим такое ребро, что оно ведёт в другую часть, то останавливаемся и говорим, что [math]uv[/math] не мост. Иначе увеличиваем уровень ребра, чтобы заново к нему не обращаться или уменьшаем уровень и повторяем процедуру. Суммарная сложность сканирования рёбер будет [math]O(|T(u)|\mathrm{\log}n)[/math], так как в худшем случае мы проверяем каждую вершину из [math]T(u)[/math], а уровень ребра не превосходит [math]\mathrm{\log}n[/math].
Общее время удаления одного ребра не превосходит [math]O(\mathrm{\log}^2{n}+S*\mathrm{\log}n)[/math], где [math]S[/math] — число неудачных сканирований, а для всех [math]m[/math] запросов получаем [math]O(\mathrm{\log}^2{n}*m+\mathrm{\log}n*\sum{S}) \leqslant O(\mathrm{\log}^2{n}*m+\mathrm{\log}n*\mathrm{\log}n*m) = O(2*\mathrm{\log}^2{n}*m)[/math], поэтому для одного запроса будем иметь время [math]O(\mathrm{\log}^2{n})[/math].
См. также
Источники информации
