Изменения

void dfs(<tex>v, parent</tex>) { <tex>enter[v] = \leftarrow return[v] = \leftarrow time</tex>++; used[v] = true; для всех вершин <tex>u </tex> смежных <tex>v</tex>: если (<tex>u == parent</tex> родитель):

если (!used[<tex>u]</tex> не посещена): stack.push(добавить в стек ребро<tex>vu);</tex> dfs(<tex>u, v</tex>); если (<tex>return[u] >= enter[v]</tex>): <tex>c = newColor()\leftarrow </tex> новый цвет пока (stack.top() ребро <tex> (vu</tex> не равно вершине стека)): <tex>color</tex>[stack.top()вершина стека] = <tex> \leftarrow c;</tex> stack.pop();извлечь вершину стека <tex>color[vu] = \leftarrow c;</tex> stack.pop();извлечь вершину стека если (<tex>return[u] < return[v]</tex>): <tex>return[v] = \leftarrow return[u];</tex> иначе: если (<tex>enter[u] < enter[v]</tex>): stack.push( добавить в стек ребро <tex>vu);</tex> если (<tex>return[v] > enter[u]</tex>): <tex>return[v] = \leftarrow return[u];</tex> } void start() { used для всех вершин заполняем false для всех <tex>v </tex> вершин графа: если (!used[<tex>v]</tex> не посещена): <tex>time = \leftarrow 0;</tex> dfs(<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>