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

Задача:

Есть неориентированный граф из [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]l(e):e{\rightarrow}[0;\mathrm{\log} n][/math] и назовём её уровнем ребра. Будем рассматривать графы [math]G_i={e|l(e) \geqslant i}\lt \tex\gt \lt !--При выполнении операции add что-то хорошее, а с удалением не всё так просто.--\gt \lt !-- === Псевдокод === xz --\gt \lt !--== Алгоритм == === Время работы === // i think i'll tell it == Частные случаи == // hahaha there is only one specific kind))0) === Деревья === //yes === Планарные графы === //da xz... chtobi o nih govorit' ischo... --\gt \lt !-- == Алгоритм == === Решение упрощённой задачи === ==== Задача без удалений рёбер ==== Если нет удалений рёбер, задачу можно решить при помощи [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]]. Каждая компонента связности {{---}} одно множество в СНМ, и при добавлении рёбер они объединяются. Время работы такого решения: \lt tex\gt O(m \cdot \alpha (n))[/math], где [math]\alpha[/math] — обратная функция Аккермана.

Построение дерева отрезков

Рассмотрим массив запросов. Каждое ребро в графе существует на некотором отрезке запросов: начиная с запроса добавления и заканчивая запросом удаления (либо концом запросов, если ребро не было удалено). Для каждого ребра можно найти этот отрезок, пройдя по массиву запросов и запоминая, когда какое ребро было добавлено.

Пусть есть [math]k[/math] рёбер, [math]i[/math]-е соединяет вершины [math]v_i[/math] и [math]u_i[/math], было добавлено запросом [math]L_i[/math] и удалено запросом [math]R_i[/math].

Построим на массиве запросов дерево отрезков, в каждой его вершине будем хранить список пар. [math]i[/math]-е рёбро графа нужно добавить на отрезок [math][L_i,R_i][/math]. Это делается аналогично тому, как в дереве отрезков происходит добавление на отрезке (процесс описан в статье "Несогласованные поддеревья. Реализация массового обновления"), но без [math]push[/math]: нужно спуститься по дереву от корня и записать пару [math]u_i,v_i[/math] в вершины дерева отрезков.

Теперь чтобы узнать, какие рёбра существуют во время выполнения [math]i[/math]-го запроса, достаточно посмотреть на путь от корня дерева отрезков до листа, который соответствует этому запросу — рёбра, записанные в вершинах этого пути, существуют во время выполнения запроса.

Ответы на запросы

Обойдём дерево отрезков в глубину, начиная с корня. Будем поддерживать граф, состоящий из рёбер, которые содержатся на пути от текущей вершины дерева отрезков до корня. При входе в вершину добавим в граф рёбра, записанные в этой вершине. При выходе из вершины нужно откатить граф к состоянию, которое было при входе. Когда мы добираемся до листа, в граф уже добавлены все рёбра, которые существуют во время выполнения соответствующего запроса, и только они. Поэтому если этот лист соответствует запросу третьего типа, его следует выполнить и сохранить ответ.

Для поддержания такого графа и ответа на запросы будем использовать систему непересекающихся множеств. При добавлении рёбер в граф объединим соответствующие множества в СНМ. Откатывание состояния СНМ описано ниже.

СНМ с откатами

Для того, чтобы иметь возможность откатывать состояние СНМ, нужно при каждом изменении любого значения в СНМ записывать в специальный массив, что именно изменилось и какое было предыдущее значение. Это можно реализовать как массив пар (указатель, значение).

Чтобы откатить состояние СНМ, пройдём по этому массиву в обратном порядке и присвоим старые значения обратно. Для лучшего понимания ознакомьтесь с приведённой ниже реализацией.

Нужно заметить, что эвристику сжатия путей в этом случае применять не следует. Эта эвристика улучшает асимптотическое время работы, но это время работы не истинное, а амортизированное. Из-за наличия откатов к предыдущим состояниям эта эвристика не даст выигрыша. СНМ с ранговой эвристикой же работает за [math]O(\log n)[/math] на запрос истинно.

Запоминание изменений и откаты не влияют на время работы, если оно истинное, а не амортизированное. Действительно: пусть в СНМ произошло [math]r[/math] изменений. Каждое из них будет один раз занесено в массив и один раз отменено. Значит, запись в массив и откаты работают за [math]\Theta(r)[/math]. Но и сами изменения заняли [math]\Theta(r)[/math] времени, значит, откаты не увеличили асимптотическое время работы.

Вместо описанного способа откатывания состояния СНМ можно использовать персистентный СНМ, но этот вариант сложнее и имеет меньшую эффективность. <!- если бы ещё псевдокод и что-то там ещё, я забыла ->

Частные случаи

1. Планарные графы. D. Eppstein доказал, что для планарных графов мы также можем выполнять запросы за [math]O(\log n)[/math].

-->

См. также

• Деревья эйлерова обхода
• Задача о динамической связности оффлайн

Источники информации

• http://se.math.spbu.ru/SE/diploma/2012/s/Kopeliovich_diploma.pdf
• Dynamic connectivity — Википедия
• http://courses.csail.mit.edu/6.851/spring12/scribe/L20.pdf
• Лекции — Академия Яндекса