読者です 読者をやめる 読者になる 読者になる

コードを短く書く人のブログ

コードゴルフを稀に取り上げるブログ

二重辺連結成分分解

ゆらふなさんの記事を見て実装してみようと思ったので記事を書きました。
この記事ではlowlinkを使った方法でやっています。

定義

  • 橋 (Bridge): その一つの辺を取り除くとグラフが非連結になるような辺
  • 二重辺連結成分 (Biedge Connected Component ?): 橋を含まないような頂点集合

内容

二重辺連結成分は橋を含まないような頂点集合なので橋を列挙することで二重辺連結成分分解ができることがわかる。
橋の検出、列挙に関しては次のpdfがわかりやすい。グラフ探索アルゴリズムとその応用
基本的には深さ優先探索をするだけで求まる。まずグラフに対して適当な頂点を決めそこから深さ優先探索を行う。

$ord[v]:$ 深さ優先探索でその頂点を何番目に訪れたか
$low[v]:$ 後退辺を一度だけ使ってたどり着ける$ord$の最小値 $(lowlink)$

とすると深さ優先探索木上の辺$uv$が橋であるかの判定は
$$ord[u] < low[v]$$ で行える。$ord$は深さ優先探索木の根方向に行けば行くほど小さくなるので$u$の子である$v$は$ord[u]<ord[v]$を満たす。
$ord[u] >= low[v]$の場合は$u$より根方向に後退辺を用いて移動できるので$u$より根方向の場合は$u$に到達できるので
$uv$が橋でないことがわかる。逆に$ord[u]<low[v]$の場合は$v$から$u$より根方向に到達できないので橋であることがわかる。
一度の深さ優先探索で橋を列挙することができるので計算量は$O(n + m)$になる。

橋を列挙できれば橋の端点から橋となる辺を使わないように深さ優先探索で二重辺連結成分を列挙できる。
ただ橋が存在しない場合は適当な頂点から深さ優先探索すると良い。
全体の計算量は$O(n + m)$になる。

実装は以下のようになった。

二重辺連結成分分解

verifyにはARC039Dを用いた。submission

ARC039D