693
правки
Изменения
→Обобщение задачи для произвольных графов
== Обобщение задачи для произвольных графов ==
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Добавление рёбер можно рассмотреть с точки зрения системы непересекающихся множеств, такой запрос будет работать за <tex>O(\mathrm{\log}n)</tex>. Операция проверки также сводится к проверке связности в остовном лесе и работает за то же самое время.
Попробуем выполнить операцию удаления ребра. Для этого в каждой компоненте связности выделим [[Остовные деревья: определения, лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес. Граф и его остовный лес {{---}} одно и то же с точки зрения связности.
Осталось проверить, является ли ребро мостом. Будем искать ребро <tex>xy</tex> на уровне <tex>l(uv)</tex>, затем <tex>l(uv)-1</tex>, <tex>l(uv)-2</tex><tex>{{...}}</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*\mathrm{\log}n)</tex>, где <tex>S</tex> {{---}} число неудачных сканирований, а для всех <tex>m</tex> запросов получаем <tex>O(\mathrm{\log}^2{n}*m+\mathrm{\log}n*\sum{S}) \leqslant O(\mathrm{\log}^2{n}*m+\mathrm{\log}n*\mathrm{\log}n*m) = O(2*\mathrm{\log}^2{n}*m), поэтому для одного запроса будем иметь время O(2*\mathrm{\log}^2{n})</tex>.
