Изменения

Используем первый проход, чтобы [[Использование обхода в глубину для поиска точек сочленения|найти ищем точки сочленения.с помощью обхода в глубину]] , заполняем массивы <tex>tin</tex> и <tex>up</tex>. <br>

[[Точка сочленения, эквивалентные определения|Точка точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязности.Вершина <tex> v \ne root </tex> является точкой сочленения, если у нее есть сын <tex> u : </tex>, такой что <tex> up[u] \geqslant tin[v] </tex>. <br> Это также значит, что ребро <tex> vu </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро по которому мы пришли в вершину <tex> v </tex> , используя поиск в глубину. Получается, что перейдя по этому ребру, мы окажемся в другой компоненте вершинной двусвязности. <br>

* Во время первого запуска <tex>dfs</tex> будут заполняться массивы <tex>tin</tex> и <tex>up</tex>, поэтому при запуске функции <tex>paint</tex> мы считаем, что они уже посчитаны.* <tex>\mathtt{| width = 100%maxColor}</tex> изначально равен <tex>0</tex>, что эквивалентно тому, что никакое ребро не окрашено.* <tex>\mathtt{color}</tex> хранит в себе цвет, компоненты, из которой вызвалась функция <tex>\mathrm{paint}</tex> для текущей вершины.|* <tex>\mathtt{parent}</tex> {{---}} это вершина, из которой мы попали в текущую.| '''function''' paint(<tex>dfsv</tex>(, color, parent): visited[<tex>v</tex>, color, parent):] = '''true''' '''for''' <tex> u : (v, u) \in E</tex>:

newColor = maxColor++maxColor

dfspaint(<tex>u</tex>, newColor, <tex>v</tex>)

dfspaint(<tex>u</tex>, color, <tex>v</tex>) '''else''' '''if''' uptin[<tex>u</tex>] <tex>\leqslant<</tex> tin[<tex>v</tex>]

  '''function''' solve(): '''for''' <tex> v \in V</tex>: dfs(<tex>v</tex>) '''for''' <tex> v \in V</tex>: '''if''' '''not''' visited[<tex>v</tex>] dfs maxColor++ paint(<tex>v</tex>, -1maxColor, -1)|width = "310px" |[[Файл:Vertex_doubleconnection_1.png‎‎|thumb|center|400px|Компоненты обозначены разным цветом]]|}<br clear = "all>

Заведем [[Стек|стек]], в который будем записывать все дуги в порядке их обработки. Если обнаружена точка сочленения, дуги очередного блока окажутся в этом стеке, начиная с дуги дерева обхода, которая привела в этот блок, до верхушки стека. <br>

'''function''' <tex>dfs</tex>paint(<tex>v</tex>, parent): enter visited[<tex>v</tex>] = '''true''' tin[<tex>\leftarrowv</tex> return] = up[<tex>v</tex>] <tex>\leftarrow</tex> = time++ '''for''' <tex> u \in V : (v, u) \in E</tex>: '''if''' <tex>u</tex> == parent '''continue''' '''if''' '''not''' visited[<tex>u</tex>] stack.push(<tex>vu</tex>) <tex>dfs</tex> paint(<tex>u, v</tex>) '''if''' returnup[<tex>u</tex>] <tex>\geqslant</tex> entertin[<tex>v</tex>] color <tex>\leftarrow </tex> = maxColor++ '''while''' stack.top() != (<tex>vu</tex>) colors[stack.top()] <tex> \leftarrow </tex> = color stack.pop() colors[<tex>vu</tex>] <tex>\leftarrow </tex> = color stack.pop() '''if''' returnup[<tex>u</tex>] < returnup[<tex>v</tex>] return up[<tex>v</tex>] <tex>\leftarrow</tex> return= up[<tex>u</tex>] '''else''' '''if''' entertin[<tex>u</tex>] < entertin[<tex>v</tex>] stack.push(<tex>vu</tex>) '''elseif''' returntin[<tex>u</tex>] < up[<tex>v</tex>] up[<tex>v</tex> enter] = tin[<tex>u</tex>] return '''else''' '''if''' up[<tex>v</tex>] > tin[<tex>\leftarrowu</tex>] up[<tex>v</tex> return] = up[<tex>u</tex>] ... '''function''' solve(): '''for''' <tex> v \in V</tex>: dfs(<tex>v</tex>) '''for''' <tex> v \in V</tex>: '''if''' '''not''' visited[<tex>v</tex>]: time <tex>\leftarrow</tex> = 0 <tex>dfs</tex> maxColor++ paint(<tex>v</tex>, -1)<br>Во время алгоритма совершается один проход <tex>dfs</tex>, который работает за <tex>O(|V | + |E|)</tex>. Внутри него совершается еще цикл, который суммарно выполняет <tex>O(|E|)</tex> операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно, общее время работы алгоритма <tex>O(|V | + |E|) + O(|E|) = O(|V | + |E|)</tex> == См. также ==* [[Использование обхода в глубину для поиска точек сочленения]]* [[Построение компонент реберной двусвязности]]