693
правки
Изменения
→Обобщение задачи для произвольных графов
При удалении возможны случаи:
* '''Удаляемое ребро является мостом'''. В этом случае дерево распадается на две части(назовём их <tex>T(u)</tex> и <tex>T(v)</tex>), и задача решается как для дерева за <tex>O(\mathrm{\log}n)</tex>.
* '''Удаляемое ребро не является мостом'''. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины <tex>u</tex> и <tex>v</tex> лежат в разных частях. Если <tex>uv</tex> принадлежало нашему лесу, то передаём эту "функцию" новому ребру.
Осталось проверить, является ли ребро мостом. Будем искать ребро <tex>xy</tex> на уровне <tex>l(xy) \ leqslant l(uv)</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>.
