Изменения

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

Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Добавление рёбер можно рассмотреть с точки зрения Для решения таких задач в каждой компоненте связности выделим [[СНМ (реализация с помощью леса корневых деревьев)Остовные деревья: определения, лемма о безопасном ребре|системы непересекающихся множествостовные деревья]], такой запрос будет работать за <tex>O(\mathrm{\log}n)</tex>которые образуют остовный лес.  [[Файл:Graph. Операция проверки сводится к проверке связности jpg|530px|thumb|left|Граф]] [[Файл:Spanforest.jpg|530px|thumb|right|Остовный лес в остовном лесе и работает также за <tex>O(\log n)</tex>.графе]]         

Введём функцию '''Замечание.''' Увеличив уровень ребра на единицу, нужно не забыть обновить <tex>l(e):eG_{\rightarrowi+1}[0;\mathrm{\log} n]</tex> и назовём её ''уровнем ребра'' <tex>eF_{i+1}</tex>. Будем рассматривать графы ====Оценка времени работы====Пункт <tex>G_i=\langle V, E\rangle: \{E | l(E) \geqslant i\}2</tex>. Очевидно, что работает за <tex>G_{\mathrm{O(\log}^2 n} \subseteq G_{\mathrm{\log}n-1} \subseteq \ldots \subseteq G_1 \subseteq G_0)</tex>. Выделим в них остовные леса таким образом, что так как после выхода из цикла мы добавляем ребро за <tex>F_{\mathrm{O(\log}n} \subseteq F_{\mathrm{\log}n-1} \subseteq \ldots \subseteq F_1 \subseteq F_0)</tex>на каждом уровне, где а количество уровней не больше <tex>F_i\log n</tex> {{.<!--5 сек, тут кажись я права всё-таки, нужен Лёха--}} остовный лес графа <tex>G_i</tex>.

[[Файл:Another_edgeПусть до момента, когда мы нашли нужное ребро, мы сделали <tex>S</tex> неудачных сканирований.jpg|200px|thumb|right]]После каждого такого сканирования нам приходится добавлять новые рёбра в <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>T(u)n</tex> вершин и <tex>Tm</tex> вызовов процедуры сложность равна <tex>O(v\log^2{n}\cdot m+\log n\cdot\displaystyle \sum_{i=1}^m S_i)</tex>), и задача решается как для дерева за что не превосходит <tex>O(\mathrmlog^2{n} \cdot m+\log n\cdot\log}n\cdot m)</tex>.* '''Удаляемое ребро не является мостом'''. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины так как уровень ребра <tex>um</tex> и раз рос максимум до <tex>v\log n</tex> лежат в разных частях). Если Отсюда суммарная сложность всех запросов равна <tex>uvO(\log^2{n}\cdot m)</tex> принадлежало нашему лесу, то передаём эту "функцию" новому ребруа для одного запроса мы решаем задачу за <tex>O(\log^2{n})</tex>.

Общее время удаления одного ребра не превосходит '''function''' <tex>O(\mathrm{\logremove}^2{n}+S</tex>('''Node''' u, '''Node''' v): '''Edge''' e = <tex>\cdotlangle </tex>u, v<tex>\mathrm{rangle</tex> '''for''' i = e.level '''downto''' 0 <tex>G_i</tex> = <tex>G_i\log}nsetminus</tex>e<!---delete(<tex>G_i</tex>, e)---> <tex>F_i</tex>, где = <tex>SF_i\setminus</tex> {{e<!---}} число неудачных просмотров ребра delete(<tex>xyF_i</tex>, а для всех e)---> '''Edge''' e2 '''for''' e2 = <tex>m\langle </tex> запросов получаем x, y<tex>O(\mathrm{rangle</tex> : e2.level == i '''and''' x <tex>\log}^2{n}in T_u</tex> '''if''' y <tex>\cdot m+in T_v</tex> '''for''' j = i '''downto''' 0 <tex>F_j</tex> = <tex>F_j</tex> <tex>\mathrm{\log}n\cdot\sum{S}cup</tex> e2<!---insert(<tex>F_i</tex>, e2) \leqslant O(\mathrm--> '''return''' '''else''' e2.level++ <tex>G_{\log}^2{n} \cdot mi+\mathrm{\log1}n\cdot\mathrm{\log}n\cdot m) </tex> = O(2\cdot\mathrm<tex>G_{\log}^2{ni+1}</tex> <tex>\cdot m)cup</tex>, поэтому для одного запроса будем иметь время e2<!---insert(<tex>O(\mathrm{\log}^2{n})F_i</tex>., e2)-->