Изменения

Перейти к: навигация, поиск

Задача о динамической связности

940 байт убрано, 00:55, 15 января 2018
Псевдокод
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>.--------->
693
правки

Навигация