Изменения

В этой статье будет приведено решение задачи online== Динамическая связность в лесах ==Если задача такова, что в графе нет и не может быть циклов, то есть отвечать на getона сводится к задаче о связности в [[Деревья Эйлерова обхода|деревьях эйлерова обхода]]. Время работы каждого запроса для упрощённой задачи {{-запрос --}} <tex>O(проверять наличие пути между вершинами\log n) мы будем сразу</tex>, где <tex>n</tex> {{---}} количество вершин в графе.

Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Но мы можем Для решения таких задач в каждой компоненте связности выделить выделим [[httpsОстовные деревья://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%81%D1%82%D0%BE%D0%B2%D0%BD%D1%8B%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D1%8C%D1%8F:_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8Fопределения,_%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D0%B1%D0%B5%D0%B7%D0%BE%D0%BF%D0%B0%D1%81%D0%BD%D0%BE%D0%BC_%D1%80%D0%B5%D0%B1%D1%80%D0%B5лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес. [[Файл:Graph.jpg|530px|thumb|left|Граф]] [[Файл:Spanforest.jpg|530px|thumb|right|Остовный лес в графе]]          

чё это значит? смотрим видосик!!===Проверка связности===Граф и его остовный лес {{---}} одно и то же с точки зрения связности. Поэтому проверка связности в графе сводится к проверке связности в остовном лесе и решается за <tex>O(\log n)</tex>.<!--Добавление рёбер можно рассмотреть с точки зрения [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], такой запрос будет работать за <tex>O(\log n)</tex>. Операция проверки сводится к проверке связности в остовном лесе и работает также за <tex>O(\log n)</tex>.-->

<!-- === Псевдокод Добавление ребра=== xz --Чтобы разобраться с тем, как изменится граф и остовный лес при добавлении и удалении ребра, введём функцию <tex>l(e):E{\rightarrow}[0;\log n]<!--== Алгоритм ===== Время работы === /tex> и назовём её ''уровнем ребра'' <tex>e</ tex>. Уровни ребра можно распределить любым способом, но для всех <tex> i think i'll tell it== Частные случаи == </tex> должно выполняться следующее свойство: размер каждой компоненты связности <tex>G_i</ hahaha there is only one specific kind))0)=== Деревья === tex> не превосходит <tex>\dfrac{n}{2^i}</tex>. Здесь графы <tex>G_i</yes === Планарные графы ==tex> определяются так: <tex>G_i= \langle V, E\rangle: \{e \in E \mid l(e) \geqslant i\}<//da xz... chtobi o nih govorit' ischotex>... -->

Очевидно, что <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>O(m \cdot rangle</tex> e.level = 0 <tex>G_0</tex> = <tex>G_0</tex> <tex>\alpha cup</tex> e<!---insert(n<tex>G_0</tex>, e)--> '''if not''' <tex>\mathrm{connected(u,v)}</tex> <tex>F_0</tex> = <tex>F_0</tex>, где <tex>\alphacup</tex> {{e<!---}} [[СНМ insert(реализация с помощью леса корневых деревьев<tex>F_0</tex>, e)#Функция Аккермана|обратная функция Аккермана]].-->

=== Построение дерева отрезков Удаление ребра==={{Утверждение|statement=Если ребро, которое мы хотим удалить, не принадлежит остовному лесу, то связность между любой парой вершин сохранится.Рассмотрим массив запросов|proof=Докажем от противного. Каждое ребро в графе существует на некотором отрезке запросов: начиная с запроса добавления и заканчивая запросом удаления (либо концом запросовДопустим, если ребро что это не было удалено)так. Для каждого Понятно, что при разрезании ребра можно найти этот отрезокнового пути между вершинами не появится.Предположим, пройдя по массиву запросов и запоминаячто нарушилась связность для каких-то двух вершин. Значит, когда какое ребро было добавленомы убрали мост. А любой мост принадлежит всем остовным деревьям его компоненты. Противоречие.}}[[Файл:Is_there_xy.jpg|200px|thumb|right|Компонента связности T.]]

Пусть есть <tex>k</tex> рёберТаким образом, если мы удалили ребро не из остовного леса, <tex>i</tex>-е соединяет вершины <tex>v_i</tex> то нам не придётся перестраивать лес и пересчитывать значение <tex>u_i</tex>\mathrm{connected(u, было добавлено запросом <tex>L_i</tex> и удалено запросом <tex>R_iv)}</tex>.

Построим на массиве запросов [[Дерево отрезков. Построение|дерево отрезков]], в каждой его вершине будем хранить список пар. <tex>i</tex>-е рёбро графа нужно добавить на отрезок <tex>[L_iРассмотрим случаи,R_i]</tex>когда мы берём ребро из леса. Это делается аналогично томуТогда необходимо выяснить, как в дереве отрезков происходит добавление на отрезке (процесс описан является ли данное ребро мостом в статье "[[Несогласованные поддеревья. Реализация массового обновления]]")графе, но без <tex>push</tex>: нужно спуститься по дереву от корня и записать пару <tex>u_i,v_i</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(\log^2 n)</tex>, так как после выхода из цикла мы добавляем ребро за <tex>O(\log n)</tex> на каждом уровне, а количество уровней не больше <tex>\log n</tex>.<!--5 сек, тут кажись я права всё-таки, нужен Лёха-->

Нужно заметитьПусть до момента, что эвристику сжатия путей когда мы нашли нужное ребро, мы сделали <tex>S</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>rm</tex> изменений. Каждое из них будет один раз занесено в массив и один раз отмененорос максимум до <tex>\log n</tex>. Значит, запись в массив и откаты работают за Отсюда суммарная сложность всех запросов равна <tex>O(\Theta(rlog^2{n}\cdot m)</tex>. Но и сами изменения заняли , а для одного запроса мы решаем задачу за <tex>O(\Theta(rlog^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, 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# Планарные графы. D. Eppstein доказал, что для планарных графов мы также можем выполнять запросы за <tex>F_j</tex> = <tex>F_j</tex> <tex>\cup</tex>Oe2<!---insert(\log n)<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)-->