Изменения

|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(m \cdot \alpha (n))</tex>определения, где <tex>\alpha</tex> {{---}} [[СНМ (реализация с помощью леса корневых деревьев)#Функция Аккерманалемма о безопасном ребре|обратная функция Аккерманаостовные деревья]], которые образуют остовный лес.

== Алгоритм ===== Построение дерева отрезков ===Рассмотрим массив запросов[[Файл:Graph.jpg|530px|thumb|left|Граф]] [[Файл:Spanforest. Каждое ребро jpg|530px|thumb|right|Остовный лес в графе существует на некотором отрезке запросов: начиная с запроса добавления и заканчивая запросом удаления (либо концом запросов, если ребро не было удалено). Для каждого ребра можно найти этот отрезок, пройдя по массиву запросов и запоминая, когда какое ребро было добавлено.]]

  === Реализация на C++ Проверка связности=== '''#include''' <bits/stdc++Граф и его остовный лес {{---}} одно и то же с точки зрения связности.hПоэтому проверка связности в графе сводится к проверке связности в остовном лесе и решается за <tex>O(\log n)</tex> '''using''' '''namespace''' std; '''typedef''' pair .<!--Добавление рёбер можно рассмотреть с точки зрения [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], такой запрос будет работать за < '''int''' , '''int''' tex> ipair; '''const''' '''int''' N = 100321; O(\log n)</tex>. Операция проверки сводится к проверке связности в остовном лесе и работает также за <font color="green"tex>// СНМO(\log n)</fonttex>.--> '''int''' dsuP[N], dsuR[N]; <font color="green">// В этот массив записываются все изменения СНМ==Добавление ребра===Чтобы разобраться с тем, как изменится граф и остовный лес при добавлении и удалении ребра, чтобы их можно откатить</font> введём функцию <font color="green">// При изменении какого-то значения в СНМ в hist записывается пара < указатель, старое значение tex>l(e):E{\rightarrow}[0;\log n]</fonttex> vector < pair < и назовём её ''уровнем ребра'int'''*, '''int''' > > hist; <font color="green"tex>e</tex>// Для элемента из СНМ возвращает корень дерева. Уровни ребра можно распределить любым способом, в котором он находитсяно для всех </fonttex> '''int''' dsuRoot('''int''' v) i </tex> должно выполняться следующее свойство: размер каждой компоненты связности <tex>G_i</tex> не превосходит <tex>\dfrac{n}{ '''while''' (dsuP[v] !2^i}</tex>. Здесь графы <tex>G_i</tex> определяются так: <tex>G_i= -1\langle V, E\rangle: \{e \in E \mid l(e) v = dsuP[v]; '''return''' v; \geqslant i\}</tex>. Очевидно, что <font color="green"tex>// Объединяет два множества. Используется ранговая эвристика.G_{\log n} \subseteq G_{\log n-1} \subseteq \ldots \subseteq G_1 \subseteq G_0 = G</fonttex> . Выделим в графах остовные леса таким образом, что <font color="green"tex>// При любом изменении содержимого массивов dsuP и dsuRF_{\log n} \subseteq F_{\log n-1} \subseteq \ldots \subseteq F_1 \subseteq F_0</fonttex> , где <font color="green"tex>// в hist записывается адрес и старое значениеF_i</fonttex> {{---}} остовный лес графа <tex>G_i</tex>. Удобнее всего новому ребру давать уровень <tex>0</tex>. В этом случае изменится только <tex>G_0</tex> '''void''' dsuMerge('''int''' a, так как в остальные подграфы <tex>G_i</tex> рёбра нулевого уровня не входят. После вставки нового ребра нам нужно проверить, были ли вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связности до того, как мы вставили ребро. Если они лежали в разных компонентах, то необходимо новое ребро добавить и в остовный лес <tex>F_0</tex>. ====Псевдокод==== ''''int''' b) { a = dsuRoot(a); b = dsuRoot(b); '''if''' (a == b) '''return'function''; ' <tex>\mathrm{add}</tex>('''Node''' u, '''ifNode''' (dsuR[a] > dsuR[b]v): { hist.emplace_back(&dsuP[b], dsuP[b]); dsuP[b] = a; } '''elseEdge''' '''if''' (dsuR[a] e = <tex>\langle </tex>u, v<tex>\rangle< dsuR[b])/tex> { e.level = 0 hist.emplace_back(&dsuP[a], dsuP[a]); dsuP[a] <tex>G_0</tex> = b; } '''else<tex>G_0</tex> <tex>\cup</tex> e<!---insert(<tex>G_0</tex>, e)--> ''' { hist.emplace_backif not''' <tex>\mathrm{connected(&dsuP[a]u, dsuP[a]v);}</tex> hist.emplace_back(&dsuR[b] <tex>F_0</tex> = <tex>F_0</tex> <tex>\cup</tex> e<!---insert(<tex>F_0</tex>, dsuR[b]e);-->  dsuP[a] = b;==Удаление ребра=== ++dsuR[b];{{Утверждение } } '''struct''' Query { '''int''' t|statement=Если ребро, которое мы хотим удалить, uне принадлежит остовному лесу, v;то связность между любой парой вершин сохранится. bool answer;|proof=Докажем от противного. Допустим, что это не так. Понятно, что при разрезании ребра нового пути между вершинами не появится. }; '''int''' nПредположим, что нарушилась связность для каких-то двух вершин. Значит, m;мы убрали мост. А любой мост принадлежит всем остовным деревьям его компоненты. Противоречие.}} Query q[N[Файл:Is_there_xy.jpg|200px|thumb|right|Компонента связности T.]]; Таким образом, если мы удалили ребро не из остовного леса, то нам не придётся перестраивать лес и пересчитывать значение <font color="green"tex>// Дерево отрезков\mathrm{connected(u, в каждой вершине которого хранится список рёберv)}</fonttex>. vector < ipair > t[N*4]; Рассмотрим случаи, когда мы берём ребро из леса. Тогда необходимо выяснить, является ли данное ребро мостом в графе, и выполнить соответствующие действия.  Проверим, является ли ребро мостом. У ребра <font color="green"tex>// Эта функция добавляет ребро на отрезокuv</fonttex> известен уровень, пусть он равен <font color="green"tex>i<// [l r] - отрезок, на который добавляется tex>. Попробуем найти другое ребро(<tex>xy</fonttex> ), соединяющее поддеревья <font color="green"tex>T_u<// uv - ребро, c - текущая вершина дерева отрезков,tex> и <tex>T_v</fonttex> , на которые распалось остовное дерево исследуемой компоненты <font color="green"tex>// [cl cr] - отрезок текущей вершины дерева отрезковT</fonttex>. '''void''' addEdge('''int''' l{{Утверждение|statement=Если ребро <tex>xy</tex> существует, '''int''' rто его уровень не больше <tex>i</tex>.|proof=От противного. Пусть <tex>l(xy)=j</tex>, ipair uv, '''int''' c, '''int''' cl, '''int''' cr) { '''if''' (l где <tex>j > i</tex>. Тогда вершины <tex>x</tex> и <tex> cr || r y< cl) '''return'''; '''if''' /tex> каким-то образом связаны в <tex>F_j</tex> (l либо непосредственно ребром <= cl && cr tex>xy<= r/tex>, либо каким-то другим путём) { t[c].push_back(uv); '''return'''; } '''int''' mid = (cl + cr) Но <tex>F_j \subseteq F_i</tex>. Значит, в <tex>F_i</ 2; addEdge(l, r, tex> между <tex>x</tex> и <tex>y</tex> сохранился путь из рёбер уровня не меньше <tex>j</tex> и появился другой путь через <tex>uv</tex>. Приходим к противоречию, c*2+1, cl, mid);так как в <tex>F_i</tex> все компоненты должны быть деревьями.}}  addEdge(l, rЧтобы найти <tex>xy</tex>, uv, c*2+2, mid+1, cr); } выберем из поддеревьев <font color="green"tex>// Обход дерева отрезков в глубинуT_u</fonttex> '''void''' go('''int''' cи <tex>T_v</tex> наименьшее. Не умаляя общности, '''int''' clбудем считать, '''int''' cr) { '''int''' startSize = hist.size(); что <font color="green"tex>// Добавляем рёбра при входе в вершину|T_u|\leqslant|T_v|</fonttex> '''for''' (ipair uv : t[c]) dsuMerge(uv.first, uv.second); '''if''' (cl == cr) { <font color="green"<!--ежу понятно-->// Если эта вершина - листТак как всегда из двух слагаемых можно выбрать одно такое, что оно не превосходит половины их суммы, то отвечаем на запросимеем важное свойство: </fonttex> '''if''' (q[cl].t |T_u|\leqslant\dfrac{|T_u|+|T_v|}{2}== 3) q[cl]\dfrac{|T|}{2}</tex>.answer = (dsuRoot(q[cl].u) == dsuRoot(q[cl].v)); Также нам известно, что <tex>T \subseteq F_i</tex>, а значит, <tex>|T|\leqslant\dfrac{n} '''else''' { '''int''' mid = (cl + cr) / 2; go(c*^i}</tex>. Отсюда <tex>|T_u|\leqslant\dfrac{n}{2^{i+1, cl, mid); go(c*2+2, mid+1, cr);}}</tex>. Это неравенство позволит нам увеличивать уровни рёбер при необходимости. } Будем искать ребро <font color="green"tex>// Откатываем изменения СНМxy</fonttex>следующим образом: '''while''' (('''int''')hist.size() # Выбираем любое ребро уровня <tex>i</tex>, выходящее из вершины, принадлежащей <tex>T_u</tex> startSize) { *hist.back().first = hist.back().second; hist.pop_back(); } } '''int''' main() { ios::sync_with_stdio('''false'''); # Если выбранное ребро ведёт в <tex>T_v</tex>, выходим из цикла и добавляем ребро <tex>xy</tex> в остовные леса <font color="green"tex>// Формат входных данных:F_i</fonttex> , для которых <font color="green"tex>i\leqslant l(xy)<// n tex> и m, затем выходим из цикла;# Если выбранное ребро ведёт в m строках запросы: по три числа t, u, vдругую вершину поддерева </fonttex> T_u<font color="green"/tex>, увеличиваем его уровень на <tex>// t - тип (1 - добавить ребро, 2 - удалить, 3 - принадлежат ли одной компоненте)</fonttex>; # Если есть непроверенные рёбра на интересующем нас уровне <font color="green"tex>i<// Нумерация вершин с нуляtex>, переходим к пункту <tex>1</fonttex>; cin # Если таких рёбер уровня <tex>i</tex> n не осталось и <tex>i> m;0</tex>, рассматриваем уровень на единицу меньший и переходим к пункту <tex>1</tex>; '''for''' ('''int''' # Если все рёбра просканированы и <tex>i = 0; i < n; ++i) /tex>, то <font color="green"tex>// Инициализация СНМuv</fonttex>является мостом.  dsuP[i] = -'''Замечание.''' Увеличив уровень ребра на единицу, нужно не забыть обновить <tex>G_{i+1; }<font color="green"/tex>// В этом массиве для каждого ещё не удалённого ребра хранитсяи <tex>F_{i+1}</fonttex>.====Оценка времени работы==== Пункт <font color="green"tex>// на каком запросе оно было создано2</fonttex> set работает за < pair tex>O(\log^2 n)< ipair/tex>, '''int''' так как после выхода из цикла мы добавляем ребро за <tex> O(\log n)</tex> edges;на каждом уровне, а количество уровней не больше <tex>\log n</tex>. '''for''' ('''int''' i = 0; i < m; ++i)!--5 сек, тут кажись я права всё-таки, нужен Лёха--> { cin Пусть до момента, когда мы нашли нужное ребро, мы сделали <tex>S</tex> q[i]неудачных сканирований.t После каждого такого сканирования нам приходится добавлять новые рёбра в <tex>> q[G_{i].u +1}</tex>> q[i].v; , что стоит <font color="green"tex>O(\log n)<// Поскольку рёбра неориентированные, u v должно означать то же самое, что и v utex>. Получаем сложность удаления одного ребра </fonttex> '''if''' O(q[i].u \log^2{n}+S\cdot\log n)</tex> q[i].v) swap(q[i]<!--- Возможно, мы удалим мост, но это уже другая история, да и она всяко лучше логарифмов в квадрате..u, q[i].v);--->  Выразим сложность одной операции <font color="green"tex>\mathrm{remove}</tex> другим способом. Для <tex>n</ При добавлении ребра кладём его в settex> вершин и <tex>m</fonttex> '''if''' вызовов процедуры сложность равна <tex>O(q[\log^2{n}\cdot m+\log n\cdot\displaystyle \sum_{i].t == 1}^m S_i) edges.emplace(ipair(q[i].u, q[i].v), i); <font color="green"/tex>, что не превосходит <tex>// При удалении ребра берём из set время его добавления - так мы узнаём отрезок заросов,O(\log^2{n} \cdot m+\log n\cdot\log n\cdot m)</fonttex> , так как уровень ребра <font color="green"tex>m</tex> раз рос максимум до <tex>\log n</ на котором оно существует. Если есть несколько одинаковых рёбер, можно брать любоеtex>.Отсюда суммарная сложность всех запросов равна <tex>O(\log^2{n}\cdot m)</fonttex> , а для одного запроса мы решаем задачу за <tex>O(\log^2{n})</tex>. ====Псевдокод====  '''elsefunction''' <tex>\mathrm{remove}</tex>('''ifNode''' (q[i].t == 2) { u, '''autoNode''' iter = edges.lower_bound(make_pair(ipair(q[i].v): '''Edge''' e = <tex>\langle </tex>u, q[i].v), 0)); addEdge(iter-<tex>second, i, iter-\rangle</tex>first, 0, 0, m - 1); edges.erase(iter); } } <font color="green">// Обрабатываем рёбра, которые не были удалены</font> ' '''for''' (i = e.level '''autodownto''' e : edges) addEdge(e.second, m - 1, e.first, 0, 0, m - 1); <font color="green"tex>// Запускаем dfs по дереву отрезковG_i</fonttex> go(0, 0, m - 1); = <font color="green"tex>// Выводим ответ.G_i\setminus</fonttex> e<!---delete(<font color="green"tex>G_i<// При обходе дерева отрезков запросы обрабатываются в том же порядке, в котором они даныtex>,e)---> <tex>F_i</fonttex> = <font color="green"tex>// поэтому ответ можно выводить прямо в go без заполнения answerF_i\setminus</fonttex> 'e<!---delete(<tex>F_i</tex>, e)---> ''for'Edge''' (e2 '''intfor''' i e2 = 0; i < m; ++tex>\langle </tex>x, y<tex>\rangle</tex> : e2.level == i) '''ifand''' (q[i].t == 3) {x <tex>\in T_u</tex> '''if''' (q[i].answer) cout y <tex>\in T_v< "YES\n";/tex> '''elsefor''' cout << "NO\n"; } j = i '''returndownto''' 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)-->

* [[СНМ (реализация с помощью леса корневых деревьев)Деревья Эйлерова обхода|Система непересекающихся множеств]]* [[Дерево отрезков. Построение|Дерево отрезковДеревья эйлерова обхода]]