Значит все дуги <tex> V' </tex> будут будут добавлены в стек после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного с ней, т.к. блоки найденные до него (если таковые имеются) будет уже извлечены из стека и покрашены в свой цвет.<br>
=== Псевдокод ===
'''function''' <tex>dfs</tex>(<tex>v</tex>, parent): enter tin[<tex>v</tex>] <tex>\leftarrow</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>(<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>) '''else''' return'''if''' up[<tex>v</tex>] > entertin[<tex>u</tex>] return up[<tex>v</tex>] <tex>\leftarrow</tex> return= up[<tex>u</tex>] ... '''for''' <tex> v \in V</tex>: '''if''' '''not''' visited[<tex>v</tex>] time <tex>\leftarrow</tex> = 0 <tex> dfs</tex>(<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>
== Источники информации ==
