Изменения

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

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

* '''Удаляемое ребро является мостом'''. В этом случае дерево распадается на две части (назовём их <tex>T(u)</tex> и <tex>T(v)</tex>), и задача решается как для дерева за <tex>O(\mathrm{\log}n)</tex>.

Осталось проверить, является ли ребро мостом. Будем искать ребро <tex>xy</tex> на уровне <tex>l(uv)</tex>, затем <tex>l(uv)-1</tex>, <tex>l(uv)-2</tex><tex>\ldots</tex>. Рассматривать будем меньшую из частей (будем считать, что <tex>|T(u)|\leqslant|T(v)|</tex>, в противном случае просто поменяем исследуемые вершины местами). Если мы находим такое ребро, что оно ведёт в другую часть, то останавливаемся и говорим, что <tex>uv</tex> не мост. Иначе увеличиваем уровень ребра, чтобы заново к нему не обращаться или уменьшаем уровень и повторяем процедуру. Суммарная сложность сканирования рёбер будет <tex>O(|T(u)|\mathrm{\log}n)</tex>, так как в худшем случае мы проверяем каждую вершину из <tex>T(u)</tex>, а уровень ребра не превосходит <tex>\mathrm{\log}n</tex>.

Общее время удаления одного ребра не превосходит <tex>O(\mathrm{\log}^2{n}+S\cdot\mathrm{\log}n)</tex>, где <tex>S</tex> {{---}} число неудачных просмотров ребра <tex>xy</tex>, а для всех <tex>m</tex> запросов получаем <tex>O(\mathrm{\log}^2{n}\cdot m+\mathrm{\log}n\cdot\sum{S}) \leqslant O(\mathrm{\log}^2{n} \cdot m+\mathrm{\log}n\cdot\mathrm{\log}n\cdot m) = O(2\cdot\mathrm{\log}^2{n}\cdot m)</tex>, поэтому для одного запроса будем иметь время <tex>O(\mathrm{\log}^2{n})</tex>.