Изменения

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

'''Второй проход:[[Точка сочленения, эквивалентные определения|Точка точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязности.Вершина <tex> v \ne root </tex> является точкой сочленения, если у нее есть сын <tex> u : return</tex>, такой что <tex> up[u] \ge entergeqslant 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{maxColor}</tex> изначально равен <tex>0</tex>, что эквивалентно тому, что никакое ребро не окрашено.* <tex>\mathtt{color}</tex> хранит в себе цвет, компоненты, из которой вызвалась функция <tex>\mathrm{| width = 100%paint}</tex> для текущей вершины.|* <tex>\mathtt{parent}</tex> {{---}} это вершина, из которой мы попали в текущую.| dfs '''function''' paint(<tex>v</tex>, ccolor, parent): visited[<tex>v</tex>)] = '''true''' для всех вершин '''for''' <tex> (v, u смежных v) \in E</tex>: если ( '''if''' <tex>u</tex> родитель) == parent переходим к следующей итерации '''continue''' если ( '''if''' '''not''' visited[<tex>u</tex> не посещена)] если ( '''if''' up[<tex>return[u</tex>] <tex>= enter[v]\geqslant</tex>) tin[<tex>c2 \leftarrowv</tex> новый цвет] newColor = ++maxColor col[<tex>col[vu] \leftarrow c2</tex>] = newColor dfs paint(<tex>u</tex>, c2newColor, <tex>v</tex>) иначе '''else''' col[<tex>col[vu] \leftarrow c</tex>] = color dfs paint(<tex>u</tex>, ccolor, <tex>v</tex>) иначе: если ( '''else''' '''if''' tin[<tex>enter[u</tex>] <= entertex><</tex> tin[<tex>v]</tex>)] col[<tex>col[vu] \leftarrow c</tex> ] = color  start '''function''' solve() для всех v вершин графа: если ( '''for''' <tex>v\in V</tex> не посещена): dfs(<tex>v, -1, -1</tex>) |width = "310px" |[[Файл:Vertex_doubleconnection_1.png‎‎|right|300px|]] '''for''' <brtex>v \in V<center/tex>: '''if''''Компоненты обозначены разным цветом''not''' visited[<tex>v</centertex>]|} maxColor++ paint(<tex>v<br clear = "all/tex>, maxColor, -1) 

В алгоритме выполняется два прохода <tex>dfs</tex>, каждый из которых работает <tex>O(|V | + |E|)</tex>. Значит время работы алгоритма <tex>O(|V | + |E|)</tex>.

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

===Доказательство корректности алгоритма===

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

==ЛитератураИсточники информации ==