212
правок
Изменения
→Однопроходный алгоритм
== Однопроходный алгоритм ==
Заведем [[Стек|стек]], в который будем записывать все дуги в порядке их обработки. Если обнаружена точка сочленения, дуги очередного блока окажутся в этом стеке, начиная с дуги дерева обхода, которая привела в этот блок, до верхушки стека. <br>
Таким образом, каждый раз находя компоненту вершинной двусвязности мы сможем покрасить все ребра, содержащиеся в ней, в новый цвет.
=== Доказательство корректности алгоритма ===
Значит все дуги <tex> V' </tex> будут будут добавлены в стек после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного с ней, т.к. блоки найденные до него (если таковые имеются) будет уже извлечены из стека и покрашены в свой цвет.<br>
=== Псевдокод ===
'''function''' <tex>dfs</tex>paint(<tex>v</tex>, parent):
tin[<tex>v</tex>] = up[<tex>v</tex>] = time++
'''for''' <tex> u : (v, u) \in E</tex>:
'''if''' <tex>u</tex> == parent
'''continue'''
'''if''' '''not''' visited[<tex>u</tex>]
stack.push(<tex>vu</tex>)
'''if''' up[<tex>u</tex>] <tex>\geqslant</tex> tin[<tex>v</tex>]
color = maxColor++
colors[stack.top()] = color
stack.pop()
colors[<tex>vu</tex>] = color
stack.pop()
'''if''' up[<tex>u</tex>] < up[<tex>v</tex>]
up[<tex>v</tex>] = up[<tex>u</tex>]
'''function''' solve(): '''for''' <tex> v \in V</tex>: '''if''' '''not''' visited[<tex>v</tex>] dfs(<tex>v</tex>) '''for''' <tex> v \in V</tex>: visited[<tex>v</tex>] = '''false''' '''for''' <tex> v \in V</tex>:
time = 0
<br>
Во время алгоритма совершается один проход <tex>dfs</tex>, который работает за <tex>O(|V| + |E|)</tex>. Внутри него совершается еще цикл, который суммарно выполняет <tex>O(|E|)</tex> операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно, общее время работы алгоритма <tex>O(|V| + |E|) + O(|E|) = O(|V| + |E|)</tex>
