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

Задача:

Есть неориентированный граф из [math]n[/math] вершин, изначально не содержащий рёбер. Требуется обработать [math]m[/math] запросов трёх типов: добавить ребро между вершинами [math]u[/math] и [math]v[/math], удалить ребро между вершинами [math]u[/math] и [math]v[/math], проверить, лежат ли вершины [math]u[/math] и [math]v[/math] в одной компоненте связности.

Алгоритм

Решение упрощённой задачи

Задача без удалений рёбер

Если нет удалений рёбер, задачу можно решить при помощи системы непересекающихся множеств. Каждая компонента связности — одно множество в СНМ, и при добавлении рёбер они объединяются.

Время работы такого решения: [math]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. Деревья. Для таких графов задачу можно решать при помощи деревьев эйлерова обхода. Операции добавления и удаления рёбер и проверка на существование пути между вершинами работают за [math]O(\log n)[/math].
2. Планарные графы. 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