Изменения

Перейти к: навигация, поиск

Задача о динамической связности оффлайн

2322 байта добавлено, 00:45, 17 января 2017
Нет описания правки
'''Динамическая связность''' (англ. ''dynamic connectivity'') {{---}} задача обработки Задача|definition = Имеется [[Основные_определения:_граф,_ребро,_вершина,_степень,_петля,_путь,_цикл#Неориентированные_графы|неориентированный граф]] из <tex>n</tex> вершин, изначально не содержащий рёбер. Требуется обработать <tex>m</tex> запросов на добавление трёх типов:* добавить ребро между вершинами <tex>u</tex> и удаление рёбер в неориентированном графе<tex>v</tex>,* удалить ребро между вершинами <tex>u</tex> и <tex>v</tex>, а также проверки* проверить, лежат ли какие-то вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связности.В графе могут быть кратные рёбра и петли.}}
В этой статье приведено решение задачи в offline, то есть ответы на все запросы будут получены после обработки всех запросов, а не по мере их поступления.
 
== Постановка задачи ==
Имеется неориентированный граф из <tex>n</tex> вершин, изначально не содержащий рёбер. Требуется обработать <tex>m</tex> запросов трёх типов:
* Добавить ребро между вершинами <tex>u</tex> и <tex>v</tex>
* Удалить ребро между вершинами <tex>u</tex> и <tex>v</tex>
* Проверить, лежат ли вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связности
В графе могут быть кратные рёбра и петли.
== Решение упрощённой задачи ==
Если нет удалений рёбер, задачу можно решить при помощи [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]]: каждая . Каждая компонента связности {{---}} это одно множество в СНМ, и при добавлении рёбер они объединяются.
Время работы такого решения: <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>u_i,v_ipush</tex> (в каждой вершине дерева хранится массив пар). Теперь чтобы узнать, какие рёбра существуют во время выполнения : нужно спуститься по дереву от корня и записать пару <tex>iu_i,v_i</tex>-го запроса, достаточно посмотреть на путь от корня в вершины дерева отрезков до листа, который соответствует этому запросу {{---}} рёбра, записанные в вершинах этого пути, существуют во время выполнения запроса.
Будем использовать систему непересекающихся множествТеперь чтобы узнать, какие рёбра существуют во время выполнения <tex>i</tex>-го запроса, достаточно посмотреть на путь от корня дерева отрезков до листа, который соответствует этому запросу {{---}} рёбра, записанные в вершинах этого пути, существуют во время выполнения запроса.  === Ответы на запросы ===Обойдём дерево отрезков в глубину, начиная с корня. Будем поддерживать граф, состоящий из рёбер, которые содержатся на пути от текущей вершины дерева отрезков до корня. При входе в вершину добавим в СНМ граф рёбра, записанные в этой вершине. При выходе из вершины нужно откатить СНМ граф к состоянию, которое было при входе (об этом ниже). Когда мы добираемся до листа, в СНМ граф уже добавлены все рёбра, которые существуют во время выполнения соответствующего запроса, и только они. Поэтому если этот лист соответствует запросу третьего типа, его следует выполнить и сохранить ответ. Для поддержания такого графа и ответа на запросы будем использовать [[СНМ (реализация с помощью леса корневых деревьев)|систему непересекающихся множеств]]. При добавлении рёбер в граф объединим соответствующие множества в СНМ. Откатывание состояния СНМ описано ниже.
=== СНМ с откатами ===
Как Для того, чтобы иметь возможность откатывать состояние СНМ? Каждый раз, когда мы изменяем что-то нужно при каждом изменении любого значения в СНМ, будем записывать в специальный массив, что именно мы изменили изменилось и какое было предыдущее значение. Это можно реализовать как массив пар (указатель, значение).
Чтобы откатить состояние СНМ, пройдём по этому массиву в обратном порядке и присвоим старые значения обратно. Для лучшего понимания ознакомьтесь с приведённой ниже реализацией.
Нужно заметить, что эвристику сжатия путей в этом случае применять не следует. Эта эвристика улучшает асимптотическое время работы, но это время работы не истинное, а амортизированное. Из-за наличия откатов к предыдущим состояниям эта эвристика не даст выигрыша. СНМ с ранговой эвристикой же работает за <tex>O(\log n)</tex> на запрос истинно.
 
Запоминание изменений и откаты не влияют на время работы, если оно истинное, а не амортизированное. Действительно: пусть в СНМ произошло <tex>r</tex> изменений. Каждое из них будет один раз занесено в массив и один раз отменено. Значит, запись в массив и откаты работают за <tex>\Theta(r)</tex>. Но и сами изменения заняли <tex>\Theta(r)</tex> времени, значит, откаты не увеличили асимптотическое время работы.
 
Вместо описанного способа откатывания состояния СНМ можно использовать [[Персистентные структуры данных|персистентный]] СНМ, но этот вариант сложнее и имеет меньшую эффективность. <!-- Я не уверен, бывает ли персистентный СНМ, работающий за log. -->
== Время работы ==
Каждое из <tex>O(m)</tex> рёбер записывается в <tex>O(\log m)</tex> вершин дерева отрезков. Поэтому операций <tex>\mathrm{union}</tex> в СНМ будет <tex>O(m \log m)</tex>. Каждая выполняется за <tex>O(\log n)</tex> (СНМ с ранговой эвристикой). Откаты не влияют на время работы.
Можно считать, что <tex>n = O(\log m)</tex>, так как в запросах используется не более <tex>2m</tex> вершин.
* Эту идею можно использовать и для других задач. Вместо СНМ можно использовать любую структуру данных, в которую можно добавлять, но не удалять.
** Например, динамический рюкзак: добавлять предмет в него можно за <tex>O(w)</tex> (<tex>w</tex> {{---}} максимальный вес), а удалять нельзя. Аналогично тому, как в dynamic connectivity offline добавляются и удаляются рёбра, можно удалять элементы из рюкзака.
 
== См. также ==
* [[СНМ (реализация с помощью леса корневых деревьев)|Система непересекающихся множеств]]
* [[Дерево отрезков. Построение|Дерево отрезков]]
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Связность в графах]]
5
правок

Навигация