5
правок
Изменения
Новая страница: «'''Динамическая связность''' (англ. ''dynamic connectivity'') {{---}} задача обработки запросов на добавл...»
'''Динамическая связность''' (англ. ''dynamic connectivity'') {{---}} задача обработки запросов на добавление и удаление рёбер в неориентированном графе, а также проверки, лежат ли какие-то вершины в одной компоненте связности.
В этой статье приведено решение задачи в 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>[L_i,R_i]</tex> разобьём на отрезки, соответствующие вершинам дерева отрезков (аналогично тому, как выполняется запрос на отрезке в дереве отрезков) и запишем в соответствующие вершины пару <tex>u_i,v_i</tex> (в каждой вершине дерева хранится массив пар). Теперь чтобы узнать, какие рёбра существуют во время выполнения <tex>i</tex>-го запроса, достаточно посмотреть на путь от корня дерева отрезков до листа, который соответствует этому запросу {{---}} рёбра, записанные в вершинах этого пути, существуют во время выполнения запроса.
Будем использовать систему непересекающихся множеств. Обойдём дерево отрезков в глубину, начиная с корня. При входе в вершину добавим в СНМ рёбра, записанные в этой вершине. При выходе из вершины нужно откатить СНМ к состоянию, которое было при входе (об этом ниже). Когда мы добираемся до листа, в СНМ уже добавлены все рёбра, которые существуют во время выполнения соответствующего запроса, и только они. Поэтому если этот лист соответствует запросу третьего типа, его следует выполнить и сохранить ответ.
=== СНМ с откатами ===
Как откатывать состояние СНМ? Каждый раз, когда мы изменяем что-то в СНМ, будем записывать в специальный массив, что именно мы изменили и какое было предыдущее значение. Это можно реализовать как массив пар (указатель, значение).
Чтобы откатить состояние СНМ, пройдём по этому массиву в обратном порядке и присвоим старые значения обратно. Для лучшего понимания ознакомьтесь с приведённой ниже реализацией.
Нужно заметить, что эвристику сжатия путей в этом случае применять не следует. Эта эвристика улучшает асимптотическое время работы, но это время работы не истинное, а амортизированное. Из-за наличия откатов к предыдущим состояниям эта эвристика не даст выигрыша. СНМ с ранговой эвристикой же работает за <tex>O(\log n)</tex> на запрос истинно.
== Время работы ==
Каждое из <tex>O(m)</tex> рёбер записывается в <tex>O(\log m)</tex> вершин дерева отрезков. Поэтому операций <tex>union</tex> в СНМ будет <tex>O(m \log m)</tex>. Каждая выполняется за <tex>O(\log n)</tex> (СНМ с ранговой эвристикой). Откаты не влияют на время работы.
Можно считать, что <tex>n = O(\log m)</tex>, так как в запросах используется не более <tex>2m</tex> вершин.
Время работы: <tex>O(m \log m \log n) = O(m \log^2 m)</tex>.
== Реализация на C++ ==
'''#include''' <bits/stdc++.h>
'''using''' '''namespace''' std;
'''typedef''' pair < '''int''' , '''int''' > ipair;
const '''int''' N = 100321;
<font color="green">// СНМ</font>
'''int''' dsuP[N], dsuR[N];
<font color="green">// В этот массив записываются все изменения СНМ, чтобы их можно откатить</font>
<font color="green">// При изменении какого-то значения в СНМ в hist записывается пара < указатель, старое значение ></font>
vector < pair < '''int'''*, '''int''' > > hist;
<font color="green">// Для элемента из СНМ возвращает корень дерева, в котором он находится</font>
'''int''' dsuRoot('''int''' v)
{
'''while''' (dsuP[v] != -1)
v = dsuP[v];
'''return''' v;
}
<font color="green">// Объединяет два множества. Используется ранговая эвристика.</font>
<font color="green">// При любом изменении содержимого массивов dsuP и dsuR</font>
<font color="green">// в hist записывается адрес и старое значение</font>
'''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];
<font color="green">// Дерево отрезков, в каждой вершине которого хранится список рёбер</font>
vector < ipair > t[N*4];
<font color="green">// Эта функция добавляет ребро на отрезок</font>
<font color="green">// [l r] - отрезок, на который добавляется ребро</font>
<font color="green">// uv - ребро, c - текущая вершина дерева отрезков,</font>
<font color="green">// [cl cr] - отрезок текущей вершины дерева отрезков</font>
'''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);
}
<font color="green">// Обход дерева отрезков в глубину</font>
'''void''' go('''int''' c, '''int''' cl, '''int''' cr)
{
'''int''' startSize = hist.size();
<font color="green">// Добавляем рёбра при входе в вершину</font>
'''for''' (ipair uv : t[c])
dsuMerge(uv.first, uv.second);
'''if''' (cl == cr)
{
<font color="green">// Если эта вершина - лист, то отвечаем на запрос</font>
'''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);
}
<font color="green">// Откатываем изменения СНМ</font>
'''while''' (('''int''')hist.size() > startSize)
{
*hist.back().first = hist.back().second;
hist.pop_back();
}
}
'''int''' main()
{
ios::sync_with_stdio('''false''');
<font color="green">// Формат входных данных:</font>
<font color="green">// n и m, затем в m строках запросы: по три числа t, u, v</font>
<font color="green">// t - тип (1 - добавить ребро, 2 - удалить, 3 - принадлежат ли одной компоненте)</font>
<font color="green">// Нумерация вершин с нуля</font>
cin >> n >> m;
'''for''' ('''int''' i = 0; i < n; ++i) <font color="green">// Инициализация СНМ</font>
dsuP[i] = -1;
<font color="green">// В этом массиве для каждого ещё не удалённого ребра хранится</font>
<font color="green">// на каком запросе оно было создано</font>
set < pair < ipair, '''int''' > > edges;
'''for''' ('''int''' i = 0; i < m; ++i)
{
cin >> q[i].t >> q[i].u >> q[i].v;
<font color="green">// Поскольку рёбра неориентированные, u v должно означать то же самое, что и v u</font>
'''if''' (q[i].u > q[i].v) swap(q[i].u, q[i].v);
<font color="green">// При добавлении ребра кладём его в set</font>
'''if''' (q[i].t == 1)
edges.emplace(ipair(q[i].u, q[i].v), i);
<font color="green">// При удалении ребра берём из set время его добавления - так мы узнаём отрезок заросов,</font>
<font color="green">// на котором оно существует. Если есть несколько одинаковых рёбер, можно брать любое.</font>
'''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);
}
}
<font color="green">// Обрабатываем рёбра, которые не были удалены</font>
'''for''' ('''auto''' e : edges)
addEdge(e.second, m - 1, e.first, 0, 0, m - 1);
<font color="green">// Запускаем dfs по дереву отрезков</font>
go(0, 0, m - 1);
<font color="green">// Выводим ответ.</font>
<font color="green">// При обходе дерева отрезков запросы обрабатываются в том же порядке, в котором они даны,</font>
<font color="green">// поэтому ответ можно выводить прямо в go без заполнения answer</font>
'''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;
}
== Замечания ==
* Дерево отрезков можно строить не на всех запросах, а только на запросах третьего типа. Это даст выигрыш по скорости и памяти, особенно если таких запросов немного по сравнению с общим числом запросов.
* Помимо проверки, лежат ли две вершины в одной компоненте связности, можно получать и другую информацию, которую можно получить из СНМ, напрмер:
** Размер компоненты связности, которая содержит вершину <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>[L_i,R_i]</tex> разобьём на отрезки, соответствующие вершинам дерева отрезков (аналогично тому, как выполняется запрос на отрезке в дереве отрезков) и запишем в соответствующие вершины пару <tex>u_i,v_i</tex> (в каждой вершине дерева хранится массив пар). Теперь чтобы узнать, какие рёбра существуют во время выполнения <tex>i</tex>-го запроса, достаточно посмотреть на путь от корня дерева отрезков до листа, который соответствует этому запросу {{---}} рёбра, записанные в вершинах этого пути, существуют во время выполнения запроса.
Будем использовать систему непересекающихся множеств. Обойдём дерево отрезков в глубину, начиная с корня. При входе в вершину добавим в СНМ рёбра, записанные в этой вершине. При выходе из вершины нужно откатить СНМ к состоянию, которое было при входе (об этом ниже). Когда мы добираемся до листа, в СНМ уже добавлены все рёбра, которые существуют во время выполнения соответствующего запроса, и только они. Поэтому если этот лист соответствует запросу третьего типа, его следует выполнить и сохранить ответ.
=== СНМ с откатами ===
Как откатывать состояние СНМ? Каждый раз, когда мы изменяем что-то в СНМ, будем записывать в специальный массив, что именно мы изменили и какое было предыдущее значение. Это можно реализовать как массив пар (указатель, значение).
Чтобы откатить состояние СНМ, пройдём по этому массиву в обратном порядке и присвоим старые значения обратно. Для лучшего понимания ознакомьтесь с приведённой ниже реализацией.
Нужно заметить, что эвристику сжатия путей в этом случае применять не следует. Эта эвристика улучшает асимптотическое время работы, но это время работы не истинное, а амортизированное. Из-за наличия откатов к предыдущим состояниям эта эвристика не даст выигрыша. СНМ с ранговой эвристикой же работает за <tex>O(\log n)</tex> на запрос истинно.
== Время работы ==
Каждое из <tex>O(m)</tex> рёбер записывается в <tex>O(\log m)</tex> вершин дерева отрезков. Поэтому операций <tex>union</tex> в СНМ будет <tex>O(m \log m)</tex>. Каждая выполняется за <tex>O(\log n)</tex> (СНМ с ранговой эвристикой). Откаты не влияют на время работы.
Можно считать, что <tex>n = O(\log m)</tex>, так как в запросах используется не более <tex>2m</tex> вершин.
Время работы: <tex>O(m \log m \log n) = O(m \log^2 m)</tex>.
== Реализация на C++ ==
'''#include''' <bits/stdc++.h>
'''using''' '''namespace''' std;
'''typedef''' pair < '''int''' , '''int''' > ipair;
const '''int''' N = 100321;
<font color="green">// СНМ</font>
'''int''' dsuP[N], dsuR[N];
<font color="green">// В этот массив записываются все изменения СНМ, чтобы их можно откатить</font>
<font color="green">// При изменении какого-то значения в СНМ в hist записывается пара < указатель, старое значение ></font>
vector < pair < '''int'''*, '''int''' > > hist;
<font color="green">// Для элемента из СНМ возвращает корень дерева, в котором он находится</font>
'''int''' dsuRoot('''int''' v)
{
'''while''' (dsuP[v] != -1)
v = dsuP[v];
'''return''' v;
}
<font color="green">// Объединяет два множества. Используется ранговая эвристика.</font>
<font color="green">// При любом изменении содержимого массивов dsuP и dsuR</font>
<font color="green">// в hist записывается адрес и старое значение</font>
'''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];
<font color="green">// Дерево отрезков, в каждой вершине которого хранится список рёбер</font>
vector < ipair > t[N*4];
<font color="green">// Эта функция добавляет ребро на отрезок</font>
<font color="green">// [l r] - отрезок, на который добавляется ребро</font>
<font color="green">// uv - ребро, c - текущая вершина дерева отрезков,</font>
<font color="green">// [cl cr] - отрезок текущей вершины дерева отрезков</font>
'''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);
}
<font color="green">// Обход дерева отрезков в глубину</font>
'''void''' go('''int''' c, '''int''' cl, '''int''' cr)
{
'''int''' startSize = hist.size();
<font color="green">// Добавляем рёбра при входе в вершину</font>
'''for''' (ipair uv : t[c])
dsuMerge(uv.first, uv.second);
'''if''' (cl == cr)
{
<font color="green">// Если эта вершина - лист, то отвечаем на запрос</font>
'''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);
}
<font color="green">// Откатываем изменения СНМ</font>
'''while''' (('''int''')hist.size() > startSize)
{
*hist.back().first = hist.back().second;
hist.pop_back();
}
}
'''int''' main()
{
ios::sync_with_stdio('''false''');
<font color="green">// Формат входных данных:</font>
<font color="green">// n и m, затем в m строках запросы: по три числа t, u, v</font>
<font color="green">// t - тип (1 - добавить ребро, 2 - удалить, 3 - принадлежат ли одной компоненте)</font>
<font color="green">// Нумерация вершин с нуля</font>
cin >> n >> m;
'''for''' ('''int''' i = 0; i < n; ++i) <font color="green">// Инициализация СНМ</font>
dsuP[i] = -1;
<font color="green">// В этом массиве для каждого ещё не удалённого ребра хранится</font>
<font color="green">// на каком запросе оно было создано</font>
set < pair < ipair, '''int''' > > edges;
'''for''' ('''int''' i = 0; i < m; ++i)
{
cin >> q[i].t >> q[i].u >> q[i].v;
<font color="green">// Поскольку рёбра неориентированные, u v должно означать то же самое, что и v u</font>
'''if''' (q[i].u > q[i].v) swap(q[i].u, q[i].v);
<font color="green">// При добавлении ребра кладём его в set</font>
'''if''' (q[i].t == 1)
edges.emplace(ipair(q[i].u, q[i].v), i);
<font color="green">// При удалении ребра берём из set время его добавления - так мы узнаём отрезок заросов,</font>
<font color="green">// на котором оно существует. Если есть несколько одинаковых рёбер, можно брать любое.</font>
'''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);
}
}
<font color="green">// Обрабатываем рёбра, которые не были удалены</font>
'''for''' ('''auto''' e : edges)
addEdge(e.second, m - 1, e.first, 0, 0, m - 1);
<font color="green">// Запускаем dfs по дереву отрезков</font>
go(0, 0, m - 1);
<font color="green">// Выводим ответ.</font>
<font color="green">// При обходе дерева отрезков запросы обрабатываются в том же порядке, в котором они даны,</font>
<font color="green">// поэтому ответ можно выводить прямо в go без заполнения answer</font>
'''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;
}
== Замечания ==
* Дерево отрезков можно строить не на всех запросах, а только на запросах третьего типа. Это даст выигрыш по скорости и памяти, особенно если таких запросов немного по сравнению с общим числом запросов.
* Помимо проверки, лежат ли две вершины в одной компоненте связности, можно получать и другую информацию, которую можно получить из СНМ, напрмер:
** Размер компоненты связности, которая содержит вершину <tex>v</tex>
** Количество компонент связности
