693
правки
Изменения
→remove(u,v)
'''Замечание.''' Увеличив уровень ребра на единицу, нужно не забыть обновить <tex>G_{i+1}</tex> и <tex>F_{i+1}</tex>.
====Псевдокод====
'''while''' i >= 0
e = <x, y>
'''for''' y : e.level == i
'''if''' y <tex>\in T_v</tex>
'''for''' j = i '''downto''' 0
insert(<tex>F_j</tex>, e)
'''break'''
'''else''' e.level++
i--
<!----При удалении возможны случаи:
* '''Удаляемое ребро является мостом'''. В этом случае дерево распадается на две части (назовём их <tex>T(u)</tex> и <tex>T(v)</tex>), и задача решается как для дерева за <tex>O(\log n)</tex>.
* '''Удаляемое ребро не является мостом'''. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины <tex>u</tex> и <tex>v</tex> лежат в разных частях). Если <tex>uv</tex> принадлежало нашему лесу, то передаём эту "функцию" новому ребру. ОЙ ВСЁ! ОЙ ВСЁ! ОЙ ВСЁ! ОЙ ВСЁ! ОЙ ВСЁ! ОЙ ВСЁ! ОЙ ВСЁ! ОЙ ВСЁ! ОЙ ВСЁ! ОЙ ВСЁ!
Общее время удаления одного ребра не превосходит <tex>O(\log^2{n}+S\cdot\log n)</tex>, где <tex>S</tex> {{---}} число неудачных просмотров ребра <tex>xy</tex>, а для всех <tex>m</tex> запросов получаем <tex>O(\log^2{n}\cdot m+\mathrm{\log}n\cdot\sum{S}) \leqslant O(\log^2{n} \cdot m+\log n\cdot\log n\cdot m) = O(2\cdot\log^2{n}\cdot m)</tex>, поэтому для одного запроса будем иметь время <tex>O(\log^2{n})</tex>.--------->
