1632
правки
Изменения
м
погодь== Динамическая связность в лесах ==Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в [[Деревья Эйлерова обхода|деревьях эйлерова обхода]]. Время работы каждого запроса для упрощённой задачи {{---}} <tex>O(\log n)</tex>, где <tex>n</tex> {{---}} количество вершин в графе.
Время Существуют задачи, в которых граф не обязательно на протяжении нашей работы такого после каждой операции добавления ребра остаётся лесом. Для решениятаких задач в каждой компоненте связности выделим [[Остовные деревья: <tex>O(m \cdot \alpha (n))</tex>определения, где <tex>\alpha</tex> {{---}} [[СНМ (реализация с помощью леса корневых деревьев)#Функция Аккерманалемма о безопасном ребре|обратная функция Аккерманаостовные деревья]], которые образуют остовный лес.
== Алгоритм ===== Построение дерева отрезков ===Рассмотрим массив запросов[[Файл:Graph.jpg|530px|thumb|left|Граф]] [[Файл:Spanforest. Каждое ребро jpg|530px|thumb|right|Остовный лес в графе существует на некотором отрезке запросов: начиная с запроса добавления и заканчивая запросом удаления (либо концом запросов, если ребро не было удалено). Для каждого ребра можно найти этот отрезок, пройдя по массиву запросов и запоминая, когда какое ребро было добавлено.]]
Пусть есть <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>push</tex>: нужно спуститься по дереву от корня и записать пару <tex>u_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(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;
}
rollbackEdits.php mass rollback
{{Задача
|definition = Имеется Есть [[Основные_определения:_граф,_ребро,_вершина,_степень,_петля,_путь,_цикл#Неориентированные_графы|неориентированный граф]] из <tex>n</tex> вершин, изначально не содержащий рёбер. Требуется обработать <tex>m</tex> запросов трёх типов:* <tex>\mathrm{add(u,v)}</tex> {{---}} добавить ребро между вершинами <tex>u</tex> и <tex>v</tex>,;* <tex>\mathrm{remove(u,v)}</tex> {{---}} удалить ребро между вершинами <tex>u</tex> и <tex>v</tex>,;* <tex>\mathrm{connected(u,v)}</tex> {{---}} проверить, лежат ли вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связности.В графе могут быть кратные рёбра и петли.
}}
== Решение упрощённой Обобщение задачи для произвольных графов ==Если нет удалений рёбер, задачу можно решить при помощи [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]]. Каждая компонента связности {{---}} одно множество в СНМ, и при добавлении рёбер они объединяются.
===Проверка связности= Замечания ==* Дерево отрезков Граф и его остовный лес {{---}} одно и то же с точки зрения связности. Поэтому проверка связности в графе сводится к проверке связности в остовном лесе и решается за <tex>O(\log n)</tex>.<!--Добавление рёбер можно строить рассмотреть с точки зрения [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], такой запрос будет работать за <tex>O(\log n)</tex>. Операция проверки сводится к проверке связности в остовном лесе и работает также за <tex>O(\log n)</tex>.--> ===Добавление ребра===Чтобы разобраться с тем, как изменится граф и остовный лес при добавлении и удалении ребра, введём функцию <tex>l(e):E{\rightarrow}[0;\log n]</tex> и назовём её ''уровнем ребра'' <tex>e</tex>. Уровни ребра можно распределить любым способом, но для всех <tex> i </tex> должно выполняться следующее свойство: размер каждой компоненты связности <tex>G_i</tex> не на всех запросахпревосходит <tex>\dfrac{n}{2^i}</tex>. Здесь графы <tex>G_i</tex> определяются так: <tex>G_i=\langle V, E\rangle: \{e \in E \mid l(e) \geqslant i\}</tex>. Очевидно, а только на запросах третьего типачто <tex>G_{\log n} \subseteq G_{\log n-1} \subseteq \ldots \subseteq G_1 \subseteq G_0 = G</tex>. Это даст выигрыш по скорости и памятиВыделим в графах остовные леса таким образом, что <tex>F_{\log n} \subseteq F_{\log n-1} \subseteq \ldots \subseteq F_1 \subseteq F_0</tex>, особенно если таких запросов немного по сравнению с общим числом запросовгде <tex>F_i</tex> {{---}} остовный лес графа <tex>G_i</tex>.* Помимо проверкиУдобнее всего новому ребру давать уровень <tex>0</tex>. В этом случае изменится только <tex>G_0</tex>, так как в остальные подграфы <tex>G_i</tex> рёбра нулевого уровня не входят. После вставки нового ребра нам нужно проверить, лежат были ли две вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связностидо того, как мы вставили ребро. Если они лежали в разных компонентах, можно получать то необходимо новое ребро добавить и другую информациюв остовный лес <tex>F_0</tex>. ====Псевдокод==== '''function''' <tex>\mathrm{add}</tex>('''Node''' u, '''Node''' v): '''Edge''' e = <tex>\langle </tex>u, v<tex>\rangle</tex> e.level = 0 <tex>G_0</tex> = <tex>G_0</tex> <tex>\cup</tex> e<!---insert(<tex>G_0</tex>, e)--> '''if not''' <tex>\mathrm{connected(u,v)}</tex> <tex>F_0</tex> = <tex>F_0</tex> <tex>\cup</tex> e<!---insert(<tex>F_0</tex>, e)--> ===Удаление ребра==={{Утверждение|statement=Если ребро, которое мы хотим удалить, не принадлежит остовному лесу, то связность между любой парой вершин сохранится.|proof=Докажем от противного. Допустим, которую можно получить из СНМчто это не так. Понятно, напрмер:что при разрезании ребра нового пути между вершинами не появится.** Размер Предположим, что нарушилась связность для каких-то двух вершин. Значит, мы убрали мост. А любой мост принадлежит всем остовным деревьям его компоненты . Противоречие.}}[[Файл:Is_there_xy.jpg|200px|thumb|right|Компонента связностиT.]] Таким образом, которая содержит вершину если мы удалили ребро не из остовного леса, то нам не придётся перестраивать лес и пересчитывать значение <tex>\mathrm{connected(u,v)}</tex>. Рассмотрим случаи, когда мы берём ребро из леса. Тогда необходимо выяснить, является ли данное ребро мостом в графе, и выполнить соответствующие действия. Проверим, является ли ребро мостом. У ребра <tex>uv</tex> известен уровень, пусть он равен <tex>i</tex>. Попробуем найти другое ребро (<tex>xy</tex>), соединяющее поддеревья <tex>T_u</tex> и <tex>T_v</tex>, на которые распалось остовное дерево исследуемой компоненты <tex>T</tex>.** Количество компонент связности* Эту идею можно использовать {{Утверждение|statement=Если ребро <tex>xy</tex> существует, то его уровень не больше <tex>i</tex>.|proof=От противного. Пусть <tex>l(xy)=j</tex>, где <tex>j > i</tex>. Тогда вершины <tex>x</tex> и <tex>y</tex> каким-то образом связаны в <tex>F_j</tex> (либо непосредственно ребром <tex>xy</tex>, либо каким-то другим путём). Но <tex>F_j \subseteq F_i</tex>. Значит, в <tex>F_i</tex> между <tex>x</tex> и <tex>y</tex> сохранился путь из рёбер уровня не меньше <tex>j</tex> и для других задачпоявился другой путь через <tex>uv</tex>. Вместо СНМ можно использовать любую структуру данныхПриходим к противоречию, так как в которую <tex>F_i</tex> все компоненты должны быть деревьями.}} Чтобы найти <tex>xy</tex>, выберем из поддеревьев <tex>T_u</tex> и <tex>T_v</tex> наименьшее. Не умаляя общности, будем считать, что <tex>|T_u|\leqslant|T_v|</tex>. <!--ежу понятно--> Так как всегда из двух слагаемых можно добавлятьвыбрать одно такое, но что оно не удалятьпревосходит половины их суммы, имеем важное свойство: <tex>|T_u|\leqslant\dfrac{|T_u|+|T_v|}{2}=\dfrac{|T|}{2}</tex>. Также нам известно, что <tex>T \subseteq F_i</tex>, а значит, <tex>|T|\leqslant\dfrac{n}{2^i}</tex>. Отсюда <tex>|T_u|\leqslant\dfrac{n}{2^{i+1}}</tex>. Это неравенство позволит нам увеличивать уровни рёбер при необходимости.** НапримерБудем искать ребро <tex>xy</tex> следующим образом:# Выбираем любое ребро уровня <tex>i</tex>, выходящее из вершины, принадлежащей <tex>T_u</tex>. # Если выбранное ребро ведёт в <tex>T_v</tex>, выходим из цикла и добавляем ребро <tex>xy</tex> в остовные леса <tex>F_i</tex>, динамический рюкзак: добавлять предмет для которых <tex>i\leqslant l(xy)</tex> и выходим из цикла;# Если выбранное ребро ведёт в него можно другую вершину поддерева <tex>T_u</tex>, увеличиваем его уровень на <tex>1</tex>;# Если есть непроверенные рёбра на интересующем нас уровне <tex>i</tex>, переходим к пункту <tex>1</tex>;# Если таких рёбер уровня <tex>i</tex> не осталось и <tex>i>0</tex>, рассматриваем уровень на единицу меньший и переходим к пункту <tex>1</tex>;# Если все рёбра просканированы и <tex>i=0</tex>, то <tex>uv</tex> является мостом. '''Замечание.''' Увеличив уровень ребра на единицу, нужно не забыть обновить <tex>G_{i+1}</tex> и <tex>F_{i+1}</tex>.====Оценка времени работы====Пункт <tex>2</tex> работает за <tex>O(w\log^2 n)</tex> , так как после выхода из цикла мы добавляем ребро за <tex>O(\log n)</tex> на каждом уровне, а количество уровней не больше <tex>\log n</tex>.<!--5 сек, тут кажись я права всё-таки, нужен Лёха--> Пусть до момента, когда мы нашли нужное ребро, мы сделали <tex>wS</tex> неудачных сканирований. После каждого такого сканирования нам приходится добавлять новые рёбра в <tex>G_{i+1}</tex>, что стоит <tex>O(\log n)</tex>. Получаем сложность удаления одного ребра <tex>O(\log^2{n}+S\cdot\log n)</tex>. <!---Возможно, мы удалим мост, но это уже другая история, да и она всяко лучше логарифмов в квадрате... ---> Выразим сложность одной операции <tex>\mathrm{remove}</tex> другим способом. Для <tex>n</tex> вершин и <tex>m</tex> вызовов процедуры сложность равна <tex>O(\log^2{n}\cdot m+\log n\cdot\displaystyle \sum_{i=1}^m S_i)</tex>, что не превосходит <tex>O(\log^2{n} \cdot m+\log n\cdot\log n\cdot m)</tex>, так как уровень ребра <tex>m</tex> раз рос максимум до <tex>\log n</tex>. Отсюда суммарная сложность всех запросов равна <tex>O(\log^2{n} максимальный вес\cdot m)</tex>, а удалять нельзядля одного запроса мы решаем задачу за <tex>O(\log^2{n})</tex>. ====Псевдокод==== '''function''' <tex>\mathrm{remove}</tex>('''Node''' u, '''Node''' v): '''Edge''' e = <tex>\langle </tex>u, v<tex>\rangle</tex> '''for''' i = e. Аналогично томуlevel '''downto''' 0 <tex>G_i</tex> = <tex>G_i\setminus</tex>e<!---delete(<tex>G_i</tex>, e)---> <tex>F_i</tex> = <tex>F_i\setminus</tex>e<!---delete(<tex>F_i</tex>, e)---> '''Edge''' e2 '''for''' e2 = <tex>\langle </tex>x, как в dynamic connectivity offline добавляются и удаляются рёбраy<tex>\rangle</tex> : e2.level == i '''and''' x <tex>\in T_u</tex> '''if''' y <tex>\in T_v</tex> '''for''' j = i '''downto''' 0 <tex>F_j</tex> = <tex>F_j</tex> <tex>\cup</tex> e2<!---insert(<tex>F_i</tex>, можно удалять элементы из рюкзакаe2)--> '''return''' '''else''' e2.level++ <tex>G_{i+1}</tex> = <tex>G_{i+1}</tex> <tex>\cup</tex> e2<!---insert(<tex>F_i</tex>, e2)-->
== См. также ==
* [[СНМ (реализация с помощью леса корневых деревьев)Деревья Эйлерова обхода|Система непересекающихся множеств]]* [[Дерево отрезков. Построение|Дерево отрезковДеревья эйлерова обхода]]
* [[Задача о динамической связности оффлайн]]
== Источники информации ==
* [https://en.wikipedia.org/wiki/Dynamic_connectivity Dynamic connectivity {{---}} Википедия]
* [http://numeralis.ru/algoritmyi-i-strukturyi-dannyih-poiska-dinamicheskaya-svyaznost-v-grafah-babenko-maksim/ Лекции {{---}} Академия Яндекса]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Связность в графах]]
