Задача о динамической связности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(remove(u,v))
м (rollbackEdits.php mass rollback)
 
(не показаны 82 промежуточные версии 3 участников)
Строка 6: Строка 6:
 
}}
 
}}
 
== Динамическая связность в лесах ==
 
== Динамическая связность в лесах ==
Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в [[Деревья Эйлерова обхода|деревьях эйлерова обхода]]. Время работы каждого запроса для упрощённой задачи {{---}} <tex>O(\log n)</tex>.
+
Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в [[Деревья Эйлерова обхода|деревьях эйлерова обхода]]. Время работы каждого запроса для упрощённой задачи {{---}} <tex>O(\log n)</tex>, где <tex>n</tex> {{---}} количество вершин в графе.
 +
 
 
== Обобщение задачи для произвольных графов ==
 
== Обобщение задачи для произвольных графов ==
  
 
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Для решения таких задач в каждой компоненте связности выделим [[Остовные деревья: определения, лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес.  
 
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Для решения таких задач в каждой компоненте связности выделим [[Остовные деревья: определения, лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес.  
Попробуем выполнить операцию удаления ребра.<!--- Для этого ---->
 
 
[[Файл:Graph.jpg|550px|thumb|left|Граф]]  [[Файл:Spanforest.jpg|550px|thumb|right|Остовный лес в графе]]
 
 
  
 +
[[Файл:Graph.jpg|530px|thumb|left|Граф]]  [[Файл:Spanforest.jpg|530px|thumb|right|Остовный лес в графе]]
  
  
Строка 31: Строка 29:
  
  
===connected(u,v)===
+
===Проверка связности===
 
Граф и его остовный лес {{---}} одно и то же с точки зрения связности. Поэтому проверка связности в графе сводится к проверке связности в остовном лесе и решается за <tex>O(\log n)</tex>.<!--Добавление рёбер можно рассмотреть с точки зрения [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], такой запрос будет работать за <tex>O(\log n)</tex>. Операция проверки сводится к проверке связности в остовном лесе и работает также за <tex>O(\log n)</tex>.-->
 
Граф и его остовный лес {{---}} одно и то же с точки зрения связности. Поэтому проверка связности в графе сводится к проверке связности в остовном лесе и решается за <tex>O(\log n)</tex>.<!--Добавление рёбер можно рассмотреть с точки зрения [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], такой запрос будет работать за <tex>O(\log n)</tex>. Операция проверки сводится к проверке связности в остовном лесе и работает также за <tex>O(\log n)</tex>.-->
  
===add(u,v)===
+
===Добавление ребра===
 
Чтобы разобраться с тем, как изменится граф и остовный лес при добавлении и удалении ребра, введём функцию <tex>l(e):E{\rightarrow}[0;\log n]</tex> и назовём её ''уровнем ребра'' <tex>e</tex>. Уровни ребра можно распределить любым способом, но для всех <tex> i </tex> должно выполняться следующее свойство: размер каждой компоненты связности <tex>G_i</tex> не превосходит <tex>\dfrac{n}{2^i}</tex>. Здесь графы <tex>G_i</tex> определяются так: <tex>G_i=\langle V, E\rangle: \{e \in E \mid l(e) \geqslant i\}</tex>.
 
Чтобы разобраться с тем, как изменится граф и остовный лес при добавлении и удалении ребра, введём функцию <tex>l(e):E{\rightarrow}[0;\log n]</tex> и назовём её ''уровнем ребра'' <tex>e</tex>. Уровни ребра можно распределить любым способом, но для всех <tex> i </tex> должно выполняться следующее свойство: размер каждой компоненты связности <tex>G_i</tex> не превосходит <tex>\dfrac{n}{2^i}</tex>. Здесь графы <tex>G_i</tex> определяются так: <tex>G_i=\langle V, E\rangle: \{e \in E \mid l(e) \geqslant i\}</tex>.
  
Строка 41: Строка 39:
 
Удобнее всего новому ребру давать уровень <tex>0</tex>. В этом случае изменится только <tex>G_0</tex>, так как в остальные подграфы <tex>G_i</tex> рёбра нулевого уровня не входят. После вставки нового ребра нам нужно проверить, были ли вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связности до того, как мы вставили ребро. Если они лежали в разных компонентах, то необходимо новое ребро добавить и в остовный лес <tex>F_0</tex>.
 
Удобнее всего новому ребру давать уровень <tex>0</tex>. В этом случае изменится только <tex>G_0</tex>, так как в остальные подграфы <tex>G_i</tex> рёбра нулевого уровня не входят. После вставки нового ребра нам нужно проверить, были ли вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связности до того, как мы вставили ребро. Если они лежали в разных компонентах, то необходимо новое ребро добавить и в остовный лес <tex>F_0</tex>.
  
<!----------  '''function''' add('''Node''' u, '''Node''' v): we need a Psevdocode-->
+
====Псевдокод====
 +
 
 +
  '''function''' <tex>\mathrm{add}</tex>('''Node''' u, '''Node''' v):
 +
    '''Edge''' e = <tex>\langle </tex>u, v<tex>\rangle</tex>
 +
    e.level = 0
 +
    <tex>G_0</tex> = <tex>G_0</tex> <tex>\cup</tex> e<!---insert(<tex>G_0</tex>, e)-->
 +
    '''if not''' <tex>\mathrm{connected(u,v)}</tex>
 +
      <tex>F_0</tex> = <tex>F_0</tex> <tex>\cup</tex> e<!---insert(<tex>F_0</tex>, e)-->
  
===remove(u,v)===
+
===Удаление ребра===
 
{{Утверждение
 
{{Утверждение
 
|statement=Если ребро, которое мы хотим удалить, не принадлежит остовному лесу, то связность между любой парой вершин сохранится.
 
|statement=Если ребро, которое мы хотим удалить, не принадлежит остовному лесу, то связность между любой парой вершин сохранится.
Строка 49: Строка 54:
 
Предположим, что нарушилась связность для каких-то двух вершин. Значит, мы убрали мост. А любой мост принадлежит всем остовным деревьям его компоненты. Противоречие.
 
Предположим, что нарушилась связность для каких-то двух вершин. Значит, мы убрали мост. А любой мост принадлежит всем остовным деревьям его компоненты. Противоречие.
 
}}
 
}}
[[Файл:Is_there_xy.jpg|200px|thumb|right]]
+
[[Файл:Is_there_xy.jpg|200px|thumb|right|Компонента связности T.]]
  
 
Таким образом, если мы удалили ребро не из остовного леса, то нам не придётся перестраивать лес и пересчитывать значение <tex>\mathrm{connected(u,v)}</tex>.
 
Таким образом, если мы удалили ребро не из остовного леса, то нам не придётся перестраивать лес и пересчитывать значение <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</tex>.
 
Проверим, является ли ребро мостом. У ребра <tex>uv</tex> известен уровень, пусть он равен <tex>i</tex>. Попробуем найти другое ребро (<tex>xy</tex>), соединяющее поддеревья <tex>T_u</tex> и <tex>T_v</tex>, на которые распалось остовное дерево исследуемой компоненты <tex>T</tex>.
  
 
{{Утверждение
 
{{Утверждение
|statement=<tex>l(xy)\leqslant i</tex>
+
|statement=Если ребро <tex>xy</tex> существует, то его уровень не больше <tex>i</tex>.
|proof=От противного. Пусть <tex>l(xy)=j</tex> и <tex>j\geqslant i</tex>. Тогда вершины <tex>x</tex> и <tex>y</tex> каким-то образом связаны в <tex>F_j</tex> (либо непосредственно ребром <tex>xy</tex>, либо каким-то другим путём). Но <tex>F_j \subseteq F_i</tex>. Значит, в <tex>F_i</tex>  между <tex>x</tex> и <tex>y</tex> сохранился путь из рёбер уровня не меньше <tex>j</tex> и появился другой путь через <tex>uv</tex>. Приходим к противоречию, так как в <tex>F_i</tex> все компоненты должны быть деревьями.
+
|proof=От противного. Пусть <tex>l(xy)=j</tex>, где <tex>j > i</tex>. Тогда вершины <tex>x</tex> и <tex>y</tex> каким-то образом связаны в <tex>F_j</tex> (либо непосредственно ребром <tex>xy</tex>, либо каким-то другим путём). Но <tex>F_j \subseteq F_i</tex>. Значит, в <tex>F_i</tex>  между <tex>x</tex> и <tex>y</tex> сохранился путь из рёбер уровня не меньше <tex>j</tex> и появился другой путь через <tex>uv</tex>. Приходим к противоречию, так как в <tex>F_i</tex> все компоненты должны быть деревьями.
 
}}
 
}}
  
Чтобы найти <tex>xy</tex>, выберем из поддеревьев <tex>T_u</tex> и <tex>T_v</tex> наименьшее. Не умаляя общности, будем считать, что <tex>|T(u)|\leqslant|T_v|</tex>. <!--ежу понятно--> Так как хотя бы одно из двух слагаемых всегда не превосходит половины их суммы, имеем важное свойство: <tex>|T(u)|\leqslant\dfrac{|T_u|+|T_v|}{2}=\dfrac{|T|}{2}</tex>. Также нам известно, что <tex>T \subseteq F_i</tex>, а значит, <tex>|T|\leqslant\dfrac{n}{2^i}</tex>. Отсюда <tex>|T(u)|\leqslant\dfrac{n}{2^{i+1}}</tex>. Это неравенство позволит нам увеличивать уровни рёбер при необходимости.
+
Чтобы найти <tex>xy</tex>, выберем из поддеревьев <tex>T_u</tex> и <tex>T_v</tex> наименьшее. Не умаляя общности, будем считать, что <tex>|T_u|\leqslant|T_v|</tex>. <!--ежу понятно--> Так как всегда из двух слагаемых можно выбрать одно такое, что оно не превосходит половины их суммы, имеем важное свойство: <tex>|T_u|\leqslant\dfrac{|T_u|+|T_v|}{2}=\dfrac{|T|}{2}</tex>. Также нам известно, что <tex>T \subseteq F_i</tex>, а значит, <tex>|T|\leqslant\dfrac{n}{2^i}</tex>. Отсюда <tex>|T_u|\leqslant\dfrac{n}{2^{i+1}}</tex>. Это неравенство позволит нам увеличивать уровни рёбер при необходимости.
 +
 
 +
Будем искать ребро <tex>xy</tex> следующим образом:
 +
# Выбираем любое ребро уровня <tex>i</tex>, выходящее из вершины, принадлежащей <tex>T_u</tex>.
 +
# Если выбранное ребро ведёт в <tex>T_v</tex>, выходим из цикла и добавляем ребро <tex>xy</tex> в остовные леса <tex>F_i</tex>, для которых <tex>i\leqslant l(xy)</tex> и выходим из цикла;
 +
# Если выбранное ребро ведёт в другую вершину поддерева <tex>T_u</tex>, увеличиваем его уровень на <tex>1</tex>;
 +
# Если есть непроверенные рёбра на интересующем нас уровне <tex>i</tex>, переходим к пункту <tex>1</tex>;
 +
# Если таких рёбер уровня <tex>i</tex> не осталось и <tex>i>0</tex>, рассматриваем уровень на единицу меньший и переходим к пункту <tex>1</tex>;
 +
# Если все рёбра просканированы и <tex>i=0</tex>, то <tex>uv</tex> является мостом.
 +
 
 +
'''Замечание.''' Увеличив уровень ребра на единицу, нужно не забыть обновить <tex>G_{i+1}</tex> и <tex>F_{i+1}</tex>.
 +
====Оценка времени работы====
 +
Пункт <tex>2</tex> работает за <tex>O(\log^2 n)</tex>, так как после выхода из цикла мы добавляем ребро за <tex>O(\log n)</tex> на каждом уровне, а количество уровней не больше <tex>\log n</tex>.
 +
<!--5 сек, тут кажись я права всё-таки, нужен Лёха-->
  
Попробуем найти подходящую вершину <tex>x</tex> в <tex>T_u</tex> следующим образом:
+
Пусть до момента, когда мы нашли нужное ребро, мы сделали <tex>S</tex> неудачных сканирований. После каждого такого сканирования нам приходится добавлять новые рёбра в <tex>G_{i+1}</tex>, что стоит <tex>O(\log n)</tex>. Получаем сложность удаления одного ребра <tex>O(\log^2{n}+S\cdot\log n)</tex>. <!--- Возможно, мы удалим мост, но это уже другая история, да и она всяко лучше логарифмов в квадрате... --->
# Если исходящее ребро ведёт в <tex>T_v</tex>, то добавляем ребро <tex>xy</tex> в остовные леса <tex>F_i</tex>, для которых <tex>i\leqslant l(xy)</tex> и выходим из цикла;
 
# Если исходящее ребро ведёт в другую вершину поддерева <tex>T_u</tex>, увеличиваем его уровень;
 
# Если есть непроверенные рёбра, переходим к пункту 1;
 
# Если таких рёбер не осталось, уменьшаем уровень на единицу и переходим к пункту 1;
 
# Если все рёбра просканированы, то <tex>xy</tex> является мостом.
 
  
<!----При удалении возможны случаи:
+
Выразим сложность одной операции <tex>\mathrm{remove}</tex> другим способом. Для <tex>n</tex> вершин и <tex>m</tex> вызовов процедуры сложность равна <tex>O(\log^2{n}\cdot m+\log n\cdot\displaystyle \sum_{i=1}^m S_i)</tex>, что не превосходит <tex>O(\log^2{n} \cdot m+\log n\cdot\log n\cdot m)</tex>, так как уровень ребра <tex>m</tex> раз рос максимум до <tex>\log n</tex>. Отсюда суммарная сложность всех запросов равна <tex>O(\log^2{n}\cdot m)</tex>, а для одного запроса мы решаем задачу за <tex>O(\log^2{n})</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>.
+
====Псевдокод====
  
Общее время удаления одного ребра не превосходит <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>.--------->
+
  '''function''' <tex>\mathrm{remove}</tex>('''Node''' u, '''Node''' v):
 +
    '''Edge''' e = <tex>\langle </tex>u, v<tex>\rangle</tex>
 +
    '''for''' i = e.level '''downto''' 0
 +
      <tex>G_i</tex> = <tex>G_i\setminus</tex>e<!---delete(<tex>G_i</tex>, e)--->
 +
      <tex>F_i</tex> = <tex>F_i\setminus</tex>e<!---delete(<tex>F_i</tex>, e)--->
 +
      '''Edge''' e2
 +
      '''for''' e2 = <tex>\langle </tex>x, y<tex>\rangle</tex> : e2.level == i '''and''' x <tex>\in T_u</tex>
 +
        '''if''' y <tex>\in T_v</tex>
 +
          '''for''' j = i '''downto''' 0
 +
            <tex>F_j</tex> = <tex>F_j</tex> <tex>\cup</tex> e2<!---insert(<tex>F_i</tex>, e2)-->
 +
          '''return'''
 +
        '''else'''
 +
          e2.level++
 +
          <tex>G_{i+1}</tex> = <tex>G_{i+1}</tex> <tex>\cup</tex> e2<!---insert(<tex>F_i</tex>, e2)-->
  
 
== См. также ==
 
== См. также ==

Текущая версия на 19:15, 4 сентября 2022

Задача:
Есть неориентированный граф из [math]n[/math] вершин, изначально не содержащий рёбер. Требуется обработать [math]m[/math] запросов трёх типов:
  • [math]\mathrm{add(u,v)}[/math] — добавить ребро между вершинами [math]u[/math] и [math]v[/math];
  • [math]\mathrm{remove(u,v)}[/math] — удалить ребро между вершинами [math]u[/math] и [math]v[/math];
  • [math]\mathrm{connected(u,v)}[/math] — проверить, лежат ли вершины [math]u[/math] и [math]v[/math] в одной компоненте связности.

Динамическая связность в лесах

Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в деревьях эйлерова обхода. Время работы каждого запроса для упрощённой задачи — [math]O(\log n)[/math], где [math]n[/math] — количество вершин в графе.

Обобщение задачи для произвольных графов

Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Для решения таких задач в каждой компоненте связности выделим остовные деревья, которые образуют остовный лес.

Граф
Остовный лес в графе









Проверка связности

Граф и его остовный лес — одно и то же с точки зрения связности. Поэтому проверка связности в графе сводится к проверке связности в остовном лесе и решается за [math]O(\log n)[/math].

Добавление ребра

Чтобы разобраться с тем, как изменится граф и остовный лес при добавлении и удалении ребра, введём функцию [math]l(e):E{\rightarrow}[0;\log n][/math] и назовём её уровнем ребра [math]e[/math]. Уровни ребра можно распределить любым способом, но для всех [math] i [/math] должно выполняться следующее свойство: размер каждой компоненты связности [math]G_i[/math] не превосходит [math]\dfrac{n}{2^i}[/math]. Здесь графы [math]G_i[/math] определяются так: [math]G_i=\langle V, E\rangle: \{e \in E \mid l(e) \geqslant i\}[/math].

Очевидно, что [math]G_{\log n} \subseteq G_{\log n-1} \subseteq \ldots \subseteq G_1 \subseteq G_0 = G[/math]. Выделим в графах остовные леса таким образом, что [math]F_{\log n} \subseteq F_{\log n-1} \subseteq \ldots \subseteq F_1 \subseteq F_0[/math], где [math]F_i[/math] — остовный лес графа [math]G_i[/math].

Удобнее всего новому ребру давать уровень [math]0[/math]. В этом случае изменится только [math]G_0[/math], так как в остальные подграфы [math]G_i[/math] рёбра нулевого уровня не входят. После вставки нового ребра нам нужно проверить, были ли вершины [math]u[/math] и [math]v[/math] в одной компоненте связности до того, как мы вставили ребро. Если они лежали в разных компонентах, то необходимо новое ребро добавить и в остовный лес [math]F_0[/math].

Псевдокод

 function [math]\mathrm{add}[/math](Node u, Node v):
   Edge e = [math]\langle [/math]u, v[math]\rangle[/math]
   e.level = 0
   [math]G_0[/math] = [math]G_0[/math] [math]\cup[/math] e
   if not [math]\mathrm{connected(u,v)}[/math]
     [math]F_0[/math] = [math]F_0[/math] [math]\cup[/math] e

Удаление ребра

Утверждение:
Если ребро, которое мы хотим удалить, не принадлежит остовному лесу, то связность между любой парой вершин сохранится.
[math]\triangleright[/math]

Докажем от противного. Допустим, что это не так. Понятно, что при разрезании ребра нового пути между вершинами не появится.

Предположим, что нарушилась связность для каких-то двух вершин. Значит, мы убрали мост. А любой мост принадлежит всем остовным деревьям его компоненты. Противоречие.
[math]\triangleleft[/math]
Компонента связности T.

Таким образом, если мы удалили ребро не из остовного леса, то нам не придётся перестраивать лес и пересчитывать значение [math]\mathrm{connected(u,v)}[/math].

Рассмотрим случаи, когда мы берём ребро из леса. Тогда необходимо выяснить, является ли данное ребро мостом в графе, и выполнить соответствующие действия.

Проверим, является ли ребро мостом. У ребра [math]uv[/math] известен уровень, пусть он равен [math]i[/math]. Попробуем найти другое ребро ([math]xy[/math]), соединяющее поддеревья [math]T_u[/math] и [math]T_v[/math], на которые распалось остовное дерево исследуемой компоненты [math]T[/math].

Утверждение:
Если ребро [math]xy[/math] существует, то его уровень не больше [math]i[/math].
[math]\triangleright[/math]
От противного. Пусть [math]l(xy)=j[/math], где [math]j \gt i[/math]. Тогда вершины [math]x[/math] и [math]y[/math] каким-то образом связаны в [math]F_j[/math] (либо непосредственно ребром [math]xy[/math], либо каким-то другим путём). Но [math]F_j \subseteq F_i[/math]. Значит, в [math]F_i[/math] между [math]x[/math] и [math]y[/math] сохранился путь из рёбер уровня не меньше [math]j[/math] и появился другой путь через [math]uv[/math]. Приходим к противоречию, так как в [math]F_i[/math] все компоненты должны быть деревьями.
[math]\triangleleft[/math]

Чтобы найти [math]xy[/math], выберем из поддеревьев [math]T_u[/math] и [math]T_v[/math] наименьшее. Не умаляя общности, будем считать, что [math]|T_u|\leqslant|T_v|[/math]. Так как всегда из двух слагаемых можно выбрать одно такое, что оно не превосходит половины их суммы, имеем важное свойство: [math]|T_u|\leqslant\dfrac{|T_u|+|T_v|}{2}=\dfrac{|T|}{2}[/math]. Также нам известно, что [math]T \subseteq F_i[/math], а значит, [math]|T|\leqslant\dfrac{n}{2^i}[/math]. Отсюда [math]|T_u|\leqslant\dfrac{n}{2^{i+1}}[/math]. Это неравенство позволит нам увеличивать уровни рёбер при необходимости.

Будем искать ребро [math]xy[/math] следующим образом:

  1. Выбираем любое ребро уровня [math]i[/math], выходящее из вершины, принадлежащей [math]T_u[/math].
  2. Если выбранное ребро ведёт в [math]T_v[/math], выходим из цикла и добавляем ребро [math]xy[/math] в остовные леса [math]F_i[/math], для которых [math]i\leqslant l(xy)[/math] и выходим из цикла;
  3. Если выбранное ребро ведёт в другую вершину поддерева [math]T_u[/math], увеличиваем его уровень на [math]1[/math];
  4. Если есть непроверенные рёбра на интересующем нас уровне [math]i[/math], переходим к пункту [math]1[/math];
  5. Если таких рёбер уровня [math]i[/math] не осталось и [math]i\gt 0[/math], рассматриваем уровень на единицу меньший и переходим к пункту [math]1[/math];
  6. Если все рёбра просканированы и [math]i=0[/math], то [math]uv[/math] является мостом.

Замечание. Увеличив уровень ребра на единицу, нужно не забыть обновить [math]G_{i+1}[/math] и [math]F_{i+1}[/math].

Оценка времени работы

Пункт [math]2[/math] работает за [math]O(\log^2 n)[/math], так как после выхода из цикла мы добавляем ребро за [math]O(\log n)[/math] на каждом уровне, а количество уровней не больше [math]\log n[/math].

Пусть до момента, когда мы нашли нужное ребро, мы сделали [math]S[/math] неудачных сканирований. После каждого такого сканирования нам приходится добавлять новые рёбра в [math]G_{i+1}[/math], что стоит [math]O(\log n)[/math]. Получаем сложность удаления одного ребра [math]O(\log^2{n}+S\cdot\log n)[/math].

Выразим сложность одной операции [math]\mathrm{remove}[/math] другим способом. Для [math]n[/math] вершин и [math]m[/math] вызовов процедуры сложность равна [math]O(\log^2{n}\cdot m+\log n\cdot\displaystyle \sum_{i=1}^m S_i)[/math], что не превосходит [math]O(\log^2{n} \cdot m+\log n\cdot\log n\cdot m)[/math], так как уровень ребра [math]m[/math] раз рос максимум до [math]\log n[/math]. Отсюда суммарная сложность всех запросов равна [math]O(\log^2{n}\cdot m)[/math], а для одного запроса мы решаем задачу за [math]O(\log^2{n})[/math].

Псевдокод

 function [math]\mathrm{remove}[/math](Node u, Node v):
   Edge e = [math]\langle [/math]u, v[math]\rangle[/math]
   for i = e.level downto 0
     [math]G_i[/math] = [math]G_i\setminus[/math]e
     [math]F_i[/math] = [math]F_i\setminus[/math]e
     Edge e2
     for e2 = [math]\langle [/math]x, y[math]\rangle[/math] : e2.level == i and x [math]\in T_u[/math]
       if y [math]\in T_v[/math] 
         for j = i downto 0
           [math]F_j[/math] = [math]F_j[/math] [math]\cup[/math] e2
         return
       else 
         e2.level++
         [math]G_{i+1}[/math] = [math]G_{i+1}[/math] [math]\cup[/math] e2

См. также

Источники информации