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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Обобщение задачи для произвольных графов)
м (rollbackEdits.php mass rollback)
 
(не показано 139 промежуточных версий 3 участников)
Строка 5: Строка 5:
 
* <tex>\mathrm{connected(u,v)}</tex> {{---}} проверить, лежат ли вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связности.
 
* <tex>\mathrm{connected(u,v)}</tex> {{---}} проверить, лежат ли вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связности.
 
}}
 
}}
В этой статье будет приведено решение задачи online, то есть отвечать на get-запрос (проверять наличие пути между вершинами) мы будем сразу.
+
== Динамическая связность в лесах ==
 +
Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в [[Деревья Эйлерова обхода|деревьях эйлерова обхода]]. Время работы каждого запроса для упрощённой задачи {{---}} <tex>O(\log n)</tex>, где <tex>n</tex> {{---}} количество вершин в графе.
  
== Динамическая связность в лесах ==
 
Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в [[Деревья Эйлерова обхода|деревьях эйлерова обхода]]. Время работы каждого запроса для упрощённой задачи {{---}} <tex>O(\log n)</tex>.
 
 
== Обобщение задачи для произвольных графов ==
 
== Обобщение задачи для произвольных графов ==
  
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Добавление рёбер можно рассмотреть с точки зрения системы непересекающихся множеств, такой запрос будет работать за <tex>O(\mathrm{\log}n)</tex>.
+
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Для решения таких задач в каждой компоненте связности выделим [[Остовные деревья: определения, лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес.  
 
 
Попробуем выполнить операцию удаления ребра. Для этого в каждой компоненте связности выделим [[Остовные деревья: определения, лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес. Граф и его остовный лес {{---}} одно и то же с точки зрения связности.
 
 
 
[[Файл:Graph.jpg|550px|thumb|left|Произвольный граф]]  [[Файл:Spanforest.jpg|550px|thumb|right|Остовный лес в графе]]
 
  
 +
[[Файл:Graph.jpg|530px|thumb|left|Граф]]  [[Файл:Spanforest.jpg|530px|thumb|right|Остовный лес в графе]]
  
  
Строка 33: Строка 29:
  
  
Введём функцию <tex>l(e):e{\rightarrow}[0;\mathrm{\log} n]</tex> и назовём её ''уровнем ребра'' <tex>e</tex>. Будем рассматривать графы <tex>G_i=\langle V, E\rangle: \{E | l(E) \geqslant i\}</tex>. Очевидно, что <tex>G_{\mathrm{\log}n} \subseteq G_{\mathrm{\log}n-1} \subseteq ... \subseteq G_1 \subseteq G_0</tex>. Выделим в них остовные леса таким образом, чтобы <tex>F_{\mathrm{\log}n} \subseteq F_{\mathrm{\log}n-1} \subseteq ... \subseteq F_1 \subseteq F_0</tex>, где <tex>F_i</tex> {{---}} остовный лес графа <tex>G_i</tex>.
+
===Проверка связности===
 +
Граф и его остовный лес {{---}} одно и то же с точки зрения связности. Поэтому проверка связности в графе сводится к проверке связности в остовном лесе и решается за <tex>O(\log n)</tex>.<!--Добавление рёбер можно рассмотреть с точки зрения [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], такой запрос будет работать за <tex>O(\log n)</tex>. Операция проверки сводится к проверке связности в остовном лесе и работает также за <tex>O(\log n)</tex>.-->
  
При удалении возможны случаи:
+
===Добавление ребра===
* '''Удаляемое ребро является мостом'''. В этом случае дерево распадается на две части, и задача решается как для дерева за <tex>O(\mathrm{\log}n)</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>.
* '''Удаляемое ребро не является мостом'''. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то разбиение множества вершин на два, при этом вершины <tex>u</tex> и <tex>v</tex> лежат в разных частях. Если <tex>uv</tex> принадлежало нашему лесу, то передаём эту "функцию" новому ребру.
 
  
Осталось узнать, как проверить, является ли ребро мостом.
+
Очевидно, что <tex>G_{\log n} \subseteq G_{\log n-1} \subseteq \ldots \subseteq G_1 \subseteq G_0 = G</tex>. Выделим в графах остовные леса таким образом, что <tex>F_{\log n} \subseteq F_{\log n-1} \subseteq \ldots \subseteq F_1 \subseteq F_0</tex>, где <tex>F_i</tex> {{---}} остовный лес графа <tex>G_i</tex>.
  
<!-- я лошара) -->
+
Удобнее всего новому ребру давать уровень <tex>0</tex>. В этом случае изменится только <tex>G_0</tex>, так как в остальные подграфы <tex>G_i</tex> рёбра нулевого уровня не входят. После вставки нового ребра нам нужно проверить, были ли вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связности до того, как мы вставили ребро. Если они лежали в разных компонентах, то необходимо новое ребро добавить и в остовный лес <tex>F_0</tex>.
<!--== Алгоритм ==
 
=== Время работы === // i think i'll tell it
 
== Частные случаи == // hahaha there is only one specific kind))0)
 
=== Деревья === //yes
 
=== Планарные графы === //da xz... chtobi o nih govorit' ischo... -->
 
<!--
 
== Алгоритм ==
 
=== Решение упрощённой задачи ===
 
==== Задача без удалений рёбер ====
 
Если нет удалений рёбер, задачу можно решить при помощи [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]]. Каждая компонента связности {{---}} одно множество в СНМ, и при добавлении рёбер они объединяются.
 
  
Время работы такого решения: <tex>O(m \cdot \alpha (n))</tex>, где <tex>\alpha</tex> {{---}} [[СНМ (реализация с помощью леса корневых деревьев)#Функция Аккермана|обратная функция Аккермана]].
+
====Псевдокод====
 +
 
 +
  '''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)-->
  
=== Построение дерева отрезков ===
+
===Удаление ребра===
Рассмотрим массив запросов. Каждое ребро в графе существует на некотором отрезке запросов: начиная с запроса добавления и заканчивая запросом удаления (либо концом запросов, если ребро не было удалено). Для каждого ребра можно найти этот отрезок, пройдя по массиву запросов и запоминая, когда какое ребро было добавлено.
+
{{Утверждение
 +
|statement=Если ребро, которое мы хотим удалить, не принадлежит остовному лесу, то связность между любой парой вершин сохранится.
 +
|proof=Докажем от противного. Допустим, что это не так. Понятно, что при разрезании ребра нового пути между вершинами не появится.
 +
Предположим, что нарушилась связность для каких-то двух вершин. Значит, мы убрали мост. А любой мост принадлежит всем остовным деревьям его компоненты. Противоречие.
 +
}}
 +
[[Файл:Is_there_xy.jpg|200px|thumb|right|Компонента связности T.]]
  
Пусть есть <tex>k</tex> рёбер, <tex>i</tex>-е соединяет вершины <tex>v_i</tex> и <tex>u_i</tex>, было добавлено запросом <tex>L_i</tex> и удалено запросом <tex>R_i</tex>.
+
Таким образом, если мы удалили ребро не из остовного леса, то нам не придётся перестраивать лес и пересчитывать значение <tex>\mathrm{connected(u,v)}</tex>.
  
Построим на массиве запросов [[Дерево отрезков. Построение|дерево отрезков]], в каждой его вершине будем хранить список пар. <tex>i</tex>-е рёбро графа нужно добавить на отрезок <tex>[L_i,R_i]</tex>. Это делается аналогично тому, как в дереве отрезков происходит добавление на отрезке (процесс описан в статье "[[Несогласованные поддеревья. Реализация массового обновления]]"), но без <tex>push</tex>: нужно спуститься по дереву от корня и записать пару <tex>u_i,v_i</tex> в вершины дерева отрезков.
+
Рассмотрим случаи, когда мы берём ребро из леса. Тогда необходимо выяснить, является ли данное ребро мостом в графе, и выполнить соответствующие действия.
  
Теперь чтобы узнать, какие рёбра существуют во время выполнения <tex>i</tex>-го запроса, достаточно посмотреть на путь от корня дерева отрезков до листа, который соответствует этому запросу {{---}} рёбра, записанные в вершинах этого пути, существуют во время выполнения запроса.
+
Проверим, является ли ребро мостом. У ребра <tex>uv</tex> известен уровень, пусть он равен <tex>i</tex>. Попробуем найти другое ребро (<tex>xy</tex>), соединяющее поддеревья <tex>T_u</tex> и <tex>T_v</tex>, на которые распалось остовное дерево исследуемой компоненты <tex>T</tex>.
  
=== Ответы на запросы ===
+
{{Утверждение
Обойдём дерево отрезков в глубину, начиная с корня. Будем поддерживать граф, состоящий из рёбер, которые содержатся на пути от текущей вершины дерева отрезков до корня. При входе в вершину добавим в граф рёбра, записанные в этой вершине. При выходе из вершины нужно откатить граф к состоянию, которое было при входе. Когда мы добираемся до листа, в граф уже добавлены все рёбра, которые существуют во время выполнения соответствующего запроса, и только они. Поэтому если этот лист соответствует запросу третьего типа, его следует выполнить и сохранить ответ.
+
|statement=Если ребро <tex>xy</tex> существует, то его уровень не больше <tex>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>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>O(\log n)</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>r</tex> изменений. Каждое из них будет один раз занесено в массив и один раз отменено. Значит, запись в массив и откаты работают за <tex>\Theta(r)</tex>. Но и сами изменения заняли <tex>\Theta(r)</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>.
  
Вместо описанного способа откатывания состояния СНМ можно использовать [[Персистентные структуры данных|персистентный]] СНМ, но этот вариант сложнее и имеет меньшую эффективность.
+
====Псевдокод====
<!- если бы ещё псевдокод и что-то там ещё, я забыла ->
 
  
=== Частные случаи ===
+
  '''function''' <tex>\mathrm{remove}</tex>('''Node''' u, '''Node''' v):
# Планарные графы. D. Eppstein доказал, что для планарных графов мы также можем выполнять запросы за <tex>O(\log n)</tex>.
+
    '''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)-->
  
 
== См. также ==
 
== См. также ==
Строка 90: Строка 108:
  
 
== Источники информации ==
 
== Источники информации ==
* [http://se.math.spbu.ru/SE/diploma/2012/s/Kopeliovich_diploma.pdf http://se.math.spbu.ru/SE/diploma/2012/s/Kopeliovich_diploma.pdf]
 
 
* [https://en.wikipedia.org/wiki/Dynamic_connectivity Dynamic connectivity {{---}} Википедия]
 
* [https://en.wikipedia.org/wiki/Dynamic_connectivity Dynamic connectivity {{---}} Википедия]
* [http://courses.csail.mit.edu/6.851/spring12/scribe/L20.pdf http://courses.csail.mit.edu/6.851/spring12/scribe/L20.pdf]
 
 
* [http://numeralis.ru/algoritmyi-i-strukturyi-dannyih-poiska-dinamicheskaya-svyaznost-v-grafah-babenko-maksim/ Лекции {{---}} Академия Яндекса]
 
* [http://numeralis.ru/algoritmyi-i-strukturyi-dannyih-poiska-dinamicheskaya-svyaznost-v-grafah-babenko-maksim/ Лекции {{---}} Академия Яндекса]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Связность в графах]]
 
[[Категория: Связность в графах]]

Текущая версия на 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

См. также

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