Изменения

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

'''Псевдокод первого проходаВторой проход: dfs([[Точка сочленения, эквивалентные определения|точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязности.Вершина <tex>v\ne root </tex>является точкой сочленения, если у нее есть сын <tex>parentu</tex>) , такой что <tex>enterup[vu] \leftarrow returngeqslant tin[v] </tex>. <br> Это также значит, что ребро <tex> vu </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро по которому мы пришли в вершину <tex> v </tex> , используя поиск в глубину. Получается, что перейдя по этому ребру, мы окажемся в другой компоненте вершинной двусвязности. <br>Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.<br>=== Псевдокод второго прохода ===* Во время первого запуска <tex>dfs</tex> будут заполняться массивы <tex>tin</tex> и <tex>up</tex>, поэтому при запуске функции <tex>paint</tex> мы считаем, что они уже посчитаны.* <tex>\leftarrow timemathtt{maxColor}</tex>++изначально равен <tex>0</tex>, что эквивалентно тому, что никакое ребро не окрашено. * <tex>\mathtt{color}</tex> хранит в себе цвет, компоненты, из которой вызвалась функция <tex>\mathrm{paint}</tex> для всех текущей вершины.* <tex>\mathtt{parent}</tex> {{---}} это вершина, из которой мы попали в текущую.  вершин '''function''' paint(<tex>uv</tex> смежных , color, parent): visited[<tex>v</tex>] = '''true''' '''for''' <tex> (v, u) \in E</tex>: если ( '''if''' <tex>u</tex> родитель) == parent переходим к следующей итерации '''continue''' если ( '''if''' '''not''' visited[<tex>u</tex> посещена)] '''if''' up[<tex>return[vu</tex>] <tex>\leftarrow min(returngeqslant</tex> tin[<tex>v</tex>], enter newColor = ++maxColor col[<tex>vu</tex>] = newColor paint(<tex>u]</tex>, newColor, <tex>v</tex>) '''else''' col[<tex>vu</tex>] = color иначе dfs paint(<tex>u</tex>, color, <tex>v</tex>) '''else''' '''if''' tin[<tex>u</tex>return[v] \leftarrow min(return<tex><</tex> tin[<tex>v</tex>], return col[u])<tex>vu</tex>] = color  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>] dfs maxColor++ paint(<tex>v, -1</tex>, maxColor, -1)

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

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

Значит все дуги <tex> V' </tex> будут будут добавлены в стеке стек после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного с ней, т.к. блоки найденный найденные до него (если таковые имеетсяимеются) будет извлечен уже извлечены из стека и помечены покрашены в свой цвет.<br>=== Псевдокод === '''Псевдокод: dfsfunction''' 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] >= enter[v]</tex>) ] <tex>c \leftarrow geqslant</tex> новый цвет пока (ребро tin[<tex>vuv</tex> не равно вершине стека] color = maxColor++ '''while''' stack.top() != (<tex>colorvu</tex>) colors[вершина стекаstack.top()] = color stack.pop() colors[<tex> \leftarrow cvu</tex>] = color извлечь вершину стека stack.pop() '''if''' up[<tex>color[vu] \leftarrow cu</tex> извлечь вершину стека если (] < up[<tex>return[u] < return[v]</tex>)] up[<tex>return[v</tex>] \leftarrow return= up[<tex>u]</tex>] иначе если ( '''else''' '''if''' tin[<tex>enter[u</tex>] < entertin[<tex>v]</tex>) ] добавить в стек ребро stack.push(<tex>vu</tex>) если ( '''if''' tin[<tex>u</tex>return] < up[<tex>v] > enter[u]</tex>)] up[<tex>return[v</tex>] \leftarrow return= tin[<tex>u]</tex>] start() для всех '''else''' '''if''' up[<tex>v</tex> вершин графа: если (] > tin[<tex>vu</tex> не посещена)] up[<tex>time \leftarrow 0v</tex> dfs(] = up[<tex>vu</tex>, -1)]

==Время работы однопроходного алгоритма== '''function''' solve():Во время алгоритма совершается один проход '''for''' <tex>dfsv \in V</tex>, который работает за : dfs(<tex>O(V + E)v</tex>. Внутри него совершается еще цикл, уоторый суммарно выполняет ) '''for''' <tex>O(E)v \in V</tex> операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно Общее время работы алгоритма : '''if''' '''not''' visited[<tex>v</tex>O(V ]: time = 0 maxColor+ E) + O paint(E) = O(V + E)<tex>v</tex>, -1)

Во время алгоритма совершается один проход <tex>dfs</tex>, который работает за <tex>O(|V| + |E|)</tex>. Внутри него совершается еще цикл, который суммарно выполняет <tex>O(|E|)</tex> операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно, общее время работы алгоритма <tex>O(|V| + |E|) + O(|E|) =O(|V| + |E|)</tex> =Литература= См. также ==* [[Использование обхода в глубину для поиска точек сочленения]]* [[Построение компонент реберной двусвязности]] == Источники информации ==