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

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

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

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

Второй проход: точка сочленения принадлежит как минимум двум компонентам вершинной двусвязности. Вершина $v \ne root$ является точкой сочленения, если у нее есть сын $u$, такой что $up[u] \geqslant tin[v]$.
Это также значит, что ребро $vu$ содержится в другой компоненте вершинной двусвязности, нежели ребро по которому мы пришли в вершину $v$ , используя поиск в глубину. Получается, что перейдя по этому ребру, мы окажемся в другой компоненте вершинной двусвязности.
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.

Псевдокод второго прохода

• $\mathtt{maxColor}$ изначально равен $0$, что эквивалентно тому, что никакое ребро не окрашено.
• $\mathtt{color}$ хранит в себе цвет, компоненты, из которой вызвалась функция $paint$ для текущей вершины.
• $\mathtt{parent}$ — это вершина, из которой мы попали в текущую.

function paint($v$, color, parent):
  for $u : (v, u) \in E$:
    if $u$ == parent
      continue
    if not visited[$u$]
      if up[$u$] $\geqslant$ tin[$v$]
        newColor = ++maxColor
        col[$vu$] = newColor
        paint($u$, newColor, $v$)
      else
        col[$vu$] = color
        paint($u$, color, $v$)
    else if up[$u$] $\leqslant$ tin[$v$]
      col[$vu$] = color

function solve():
  for $v \in V$:
    dfs($v$)    
  for $v \in V$:
    if not visited[$v$]
      maxColor++
      paint($v$, maxColor, -1)

Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.
В алгоритме выполняется два прохода $dfs$, каждый из которых работает $O(|V| + |E|)$. Значит время работы алгоритма $O(|V| + |E|)$.

Однопроходный алгоритм

Заведем стек, в который будем записывать все дуги в порядке их обработки. Если обнаружена точка сочленения, дуги очередного блока окажутся в этом стеке, начиная с дуги дерева обхода, которая привела в этот блок, до верхушки стека.
Таким образом, каждый раз находя компоненту вершинной двусвязности мы сможем покрасить все ребра, содержащиеся в ней, в новый цвет.

Доказательство корректности алгоритма

Предположим, что граф содержит точку сочленения $i' \in V$ , за которой следует один или несколько блоков. Вершины из этих блоков образуют подмножество $V' \subset V$. В таком случае:

1. Все вершины $V'$ являются потомками $i'$ в дереве обхода;
2. Все вершины $V'$ будут пройдены в течение периода серого состояния $i'$;
3. В $G$ не может быть обратных дуг из $V'$ в $V \setminus V'$.
   

Значит все дуги $V'$ будут будут добавлены в стек после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного с ней, т.к. блоки найденные до него (если таковые имеются) будет уже извлечены из стека и покрашены в свой цвет.

Псевдокод

function paint($v$, parent):
  tin[$v$] = up[$v$] = time++
  for $(v, u) \in E$:
    if $u$ == parent 
      continue
    if not visited[$u$]
      stack.push($vu$)
      paint($u, v$)
      if up[$u$] $\geqslant$ tin[$v$]
        color = maxColor++
        while stack.top() != ($vu$)
          colors[stack.top()] = color
          stack.pop()
        colors[$vu$] = color
        stack.pop()
      if up[$u$] < up[$v$]
        up[$v$] = up[$u$]
    else if tin[$u$] < tin[$v$] 
      stack.push($vu$)
    else if up[$v$] > tin[$u$]
      up[$v$] = up[$u$]

function solve():
  for $v \in V$:
    dfs($v$)
  for $v \in V$:
    if not visited[$v$]:
      time = 0
      maxColor++
      paint($v$, -1)

Во время алгоритма совершается один проход $dfs$, который работает за $O(|V| + |E|)$. Внутри него совершается еще цикл, который суммарно выполняет $O(|E|)$ операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно, общее время работы алгоритма $O(|V| + |E|) + O(|E|) = O(|V| + |E|)$

См. также

• Использование обхода в глубину для поиска точек сочленения
• Построение компонент реберной двусвязности

Источники информации

• В.А.Кузнецов, А.М.Караваев. "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007
• Дискретная математика: Алгоритмы — Компоненты двусвязности, мосты и точки сочленения