693
правки
Изменения
→remove(u,v)
Предположим, что нарушилась связность для каких-то двух вершин. Значит, мы убрали мост. А любой мост принадлежит всем остовным деревьям его компоненты. Противоречие.
}}
[[Файл:Another_edgeIs_there_xy.jpg|200px|thumb|right]]
Таким образом, если мы удалили ребро не из остовного леса, то нам не придётся перестраивать лес и пересчитывать значение <tex>\mathrm{connected(u,v)}</tex>.
Рассмотрим случаи, когда мы берём ребро из леса. Тогда необходимо выяснить, не является ли данное ребро мостом в графе, и выполнить соответствующие действия. Проверим, является ли ребро. У ребра <tex>uv</tex> известен уровень, пусть он равен <tex>i</tex>. Попробуем найти другое ребро (<tex>xy</tex>), соединяющее поддеревья <tex>T_u</tex> и <tex>T_v</tex>, на которые распалось остовное дерево исследуемой компоненты.===== =Проверка= =====
<!----При удалении возможны случаи:
* '''Удаляемое ребро является мостом'''. В этом случае дерево распадается на две части (назовём их <tex>T(u)</tex> и <tex>T(v)</tex>), и задача решается как для дерева за <tex>O(\log n)</tex>.
* '''Удаляемое ребро не является мостом'''. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины <tex>u</tex> и <tex>v</tex> лежат в разных частях). Если <tex>uv</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)|\cdot\log n)</tex>, так как в худшем случае мы проверяем каждую вершину из <tex>T(u)</tex>, а уровень ребра не превосходит <tex>\log n</tex>.
