Изменения

Построение компонент вершинной двусвязности будем осуществлять с помощью обхода в глубину.

==Двупроходный алгоритм==

Используем первый проход, чтобы [[Использование обхода в глубину для поиска точек сочленения|найти точки сочленения.]] <br>

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

}

[[Точка сочленения, эквивалентные определения|Точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязности.

Вершина <tex> v \ne root </tex> является точкой сочленения, если у нее <tex> \exists </tex> непосредственный сын <tex> u : return[u] \ge enter[v] </tex>. <br> Это так же значит, что ребро <tex> vu </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро, по которому мы пришли в вершину <tex> v </tex> , используя поиск в глубину. <br>

# Все вершины <tex> V' </tex> будут пройдены в течение периода серого состояния <tex> i' </tex>.

При этом в <tex> G </tex> не может быть обратных дуг из <tex> V' </tex> в <tex> V \setminus V' </tex>. Воспользуемся этим.

void dfs(v, parent) {

enter[v] = return[v] = time++;