Задача о динамической связности оффлайн
Динамическая связность (англ. dynamic connectivity) — задача обработки запросов на добавление и удаление рёбер в неориентированном графе, а также проверки, лежат ли какие-то вершины в одной компоненте связности.
В этой статье приведено решение задачи в offline, то есть ответы на все запросы будут получены после обработки всех запросов, а не по мере их поступления.
Постановка задачи
Имеется неориентированный граф из вершин, изначально не содержащий рёбер. Требуется обработать запросов трёх типов:
- Добавить ребро между вершинами и
- Удалить ребро между вершинами и
- Проверить, лежат ли вершины и в одной компоненте связности
В графе могут быть кратные рёбра и петли.
Решение упрощённой задачи
Если нет удалений рёбер, задачу можно решить при помощи системы непересекающихся множеств: каждая компонента связности — это одно множество в СНМ, и при добавлении рёбер они объединяются.
Время работы такого решения: , где — обратная функция Аккермана.
Алгоритм
Рассмотрим массив запросов. Каждое ребро в графе существует на некотором отрезке запросов: начиная с запроса добавления и заканчивая запросом удаления (либо концом запросов, если ребро не было удалено). Для каждого ребра можно найти этот отрезок, пройдя по массиву запросов и запоминая, когда какое ребро было добавлено.
Пусть есть рёбер, -е соединяет вершины и , было добавлено запросом и удалено запросом .
Построим на массиве запросов дерево отрезков. Каждый из отрезков разобьём на отрезки, соответствующие вершинам дерева отрезков (аналогично тому, как выполняется запрос на отрезке в дереве отрезков) и запишем в соответствующие вершины пару (в каждой вершине дерева хранится массив пар). Теперь чтобы узнать, какие рёбра существуют во время выполнения -го запроса, достаточно посмотреть на путь от корня дерева отрезков до листа, который соответствует этому запросу — рёбра, записанные в вершинах этого пути, существуют во время выполнения запроса.
Будем использовать систему непересекающихся множеств. Обойдём дерево отрезков в глубину, начиная с корня. При входе в вершину добавим в СНМ рёбра, записанные в этой вершине. При выходе из вершины нужно откатить СНМ к состоянию, которое было при входе (об этом ниже). Когда мы добираемся до листа, в СНМ уже добавлены все рёбра, которые существуют во время выполнения соответствующего запроса, и только они. Поэтому если этот лист соответствует запросу третьего типа, его следует выполнить и сохранить ответ.
СНМ с откатами
Как откатывать состояние СНМ? Каждый раз, когда мы изменяем что-то в СНМ, будем записывать в специальный массив, что именно мы изменили и какое было предыдущее значение. Это можно реализовать как массив пар (указатель, значение).
Чтобы откатить состояние СНМ, пройдём по этому массиву в обратном порядке и присвоим старые значения обратно. Для лучшего понимания ознакомьтесь с приведённой ниже реализацией.
Нужно заметить, что эвристику сжатия путей в этом случае применять не следует. Эта эвристика улучшает асимптотическое время работы, но это время работы не истинное, а амортизированное. Из-за наличия откатов к предыдущим состояниям эта эвристика не даст выигрыша. СНМ с ранговой эвристикой же работает за на запрос истинно.
Время работы
Каждое из рёбер записывается в вершин дерева отрезков. Поэтому операций в СНМ будет . Каждая выполняется за (СНМ с ранговой эвристикой). Откаты не влияют на время работы.
Можно считать, что , так как в запросах используется не более вершин.
Время работы: .
Реализация на C++
#include <bits/stdc++.h>
using namespace std;
typedef pair < int , int > ipair;
const int N = 100321;
// СНМ
int dsuP[N], dsuR[N];
// В этот массив записываются все изменения СНМ, чтобы их можно откатить
// При изменении какого-то значения в СНМ в hist записывается пара < указатель, старое значение >
vector < pair < int*, int > > hist;
// Для элемента из СНМ возвращает корень дерева, в котором он находится
int dsuRoot(int v)
{
while (dsuP[v] != -1)
v = dsuP[v];
return v;
}
// Объединяет два множества. Используется ранговая эвристика.
// При любом изменении содержимого массивов dsuP и dsuR
// в hist записывается адрес и старое значение
void dsuMerge(int a, int b)
{
a = dsuRoot(a);
b = dsuRoot(b);
if (a == b)
return;
if (dsuR[a] > dsuR[b])
{
hist.emplace_back(&dsuP[b], dsuP[b]);
dsuP[b] = a;
} else if (dsuR[a] < dsuR[b])
{
hist.emplace_back(&dsuP[a], dsuP[a]);
dsuP[a] = b;
} else
{
hist.emplace_back(&dsuP[a], dsuP[a]);
hist.emplace_back(&dsuR[b], dsuR[b]);
dsuP[a] = b;
++dsuR[b];
}
}
struct Query
{
int t, u, v;
bool answer;
};
int n, m;
Query q[N];
// Дерево отрезков, в каждой вершине которого хранится список рёбер
vector < ipair > t[N*4];
// Эта функция добавляет ребро на отрезок
// [l r] - отрезок, на который добавляется ребро
// uv - ребро, c - текущая вершина дерева отрезков,
// [cl cr] - отрезок текущей вершины дерева отрезков
void addEdge(int l, int r, ipair uv, int c, int cl, int cr)
{
if (l > cr || r < cl)
return;
if (l <= cl && cr <= r)
{
t[c].push_back(uv);
return;
}
int mid = (cl + cr) / 2;
addEdge(l, r, uv, c*2+1, cl, mid);
addEdge(l, r, uv, c*2+2, mid+1, cr);
}
// Обход дерева отрезков в глубину
void go(int c, int cl, int cr)
{
int startSize = hist.size();
// Добавляем рёбра при входе в вершину
for (ipair uv : t[c])
dsuMerge(uv.first, uv.second);
if (cl == cr)
{
// Если эта вершина - лист, то отвечаем на запрос
if (q[cl].t == 3)
q[cl].answer = (dsuRoot(q[cl].u) == dsuRoot(q[cl].v));
} else {
int mid = (cl + cr) / 2;
go(c*2+1, cl, mid);
go(c*2+2, mid+1, cr);
}
// Откатываем изменения СНМ
while ((int)hist.size() > startSize)
{
*hist.back().first = hist.back().second;
hist.pop_back();
}
}
int main()
{
ios::sync_with_stdio(false);
// Формат входных данных:
// n и m, затем в m строках запросы: по три числа t, u, v
// t - тип (1 - добавить ребро, 2 - удалить, 3 - принадлежат ли одной компоненте)
// Нумерация вершин с нуля
cin >> n >> m;
for (int i = 0; i < n; ++i) // Инициализация СНМ
dsuP[i] = -1;
// В этом массиве для каждого ещё не удалённого ребра хранится
// на каком запросе оно было создано
set < pair < ipair, int > > edges;
for (int i = 0; i < m; ++i)
{
cin >> q[i].t >> q[i].u >> q[i].v;
// Поскольку рёбра неориентированные, u v должно означать то же самое, что и v u
if (q[i].u > q[i].v) swap(q[i].u, q[i].v);
// При добавлении ребра кладём его в set
if (q[i].t == 1)
edges.emplace(ipair(q[i].u, q[i].v), i);
// При удалении ребра берём из set время его добавления - так мы узнаём отрезок заросов,
// на котором оно существует. Если есть несколько одинаковых рёбер, можно брать любое.
else if (q[i].t == 2)
{
auto iter = edges.lower_bound(make_pair(ipair(q[i].u, q[i].v), 0));
addEdge(iter->second, i, iter->first, 0, 0, m - 1);
edges.erase(iter);
}
}
// Обрабатываем рёбра, которые не были удалены
for (auto e : edges)
addEdge(e.second, m - 1, e.first, 0, 0, m - 1);
// Запускаем dfs по дереву отрезков
go(0, 0, m - 1);
// Выводим ответ.
// При обходе дерева отрезков запросы обрабатываются в том же порядке, в котором они даны,
// поэтому ответ можно выводить прямо в go без заполнения answer
for (int i = 0; i < m; ++i)
if (q[i].t == 3)
{
if (q[i].answer)
cout << "YES\n";
else
cout << "NO\n";
}
return 0;
}
Замечания
- Дерево отрезков можно строить не на всех запросах, а только на запросах третьего типа. Это даст выигрыш по скорости и памяти, особенно если таких запросов немного по сравнению с общим числом запросов.
- Помимо проверки, лежат ли две вершины в одной компоненте связности, можно получать и другую информацию, которую можно получить из СНМ, напрмер:
- Размер компоненты связности, которая содержит вершину
- Количество компонент связности
- Эту идею можно использовать и для других задач. Вместо СНМ можно использовать любую структуру данных, в которую можно добавлять, но не удалять.
- Например, динамический рюкзак: добавлять предмет в него можно за ( — максимальный вес), а удалять нельзя. Аналогично тому, как в dynamic connectivity offline добавляются и удаляются рёбра, можно удалять элементы из рюкзака.
