Построение компонент вершинной двусвязности

Определение

Определение:

Компонентой вершинной двусвязности графа [math]G(V, E)[/math] называется подмножество ребер [math] S \subset E [/math], такое что любые два ребра из него лежат на вершинно простом цикле.

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

Первый проход

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

   void dfs(v, parent) {
       enter[v] = return[v] = time++;
       used[v] = true;
       для всех  вершин u смежных v:
           если (u == parent): 
               переходим к следующей итерации
           если (used[u]):
               return[v] := min(return[v], enter[u]);
           иначе:
               dfs(u, v);
               return[v] := min(return[v], return[u]);
   }
   void start() {
       used для всех вершин заполняем false
       для всех v вершин графа:
           если (!used[v]):
               time = 0;
               dfs(v, -1);
   }

Точка сочленения принадлежит как минимум двум компонентам вершинной двусвязаности. Вершина [math] u \ne root [/math] является точкой сочленения, если у нее [math] \exists [/math] непосредственный сын [math] v : return[v]\ge enter[u] [/math].
Это так же значит, что ребро [math] uv [/math] содержится в другой компоненте вершинной двусвязности, нежели ребро, по которому мы пришли в вершину [math] v [/math] , используя поиск в глубину.
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.
Псевдокод второго прохода:

   void dfs(v, c, parent) {
       used[v] = true;
       для всех  вершин u смежных v:
           если (u == parent): 
               переходим к следующей итерации
           если (!used[u]):
               если (return[u] >= enter[v]):
                   с2 = newColor();
                   col[vu] = c2;
                   dfs(u, c2, v);
               иначе:
                   col[vu] = c;
                   dfs(u, c, v);
           иначе:
               если (enter[u] <= enter[v]):
                   col[vu] = c;          
   }
   void start() {
       c = 0;
       used для всех вершин заполняем false;
       для всех v вершин графа:
           если (!used[v]):
               dfs(v, c, -1);
   }

Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.