二辺連結成分分解
ゆらふなさんの記事を見て実装してみようと思ったので記事を書きました。
この記事ではlowlinkを使った方法でやっています。
* 2017年9月30日追記 *
二重辺と表記していましたが二辺と表現するほうが適切と判断したので変更しました.
それに付随して定義などの情報を追加しました.
定義
- 橋 (Bridge): その一つの辺を取り除くとグラフが非連結になるような辺
- K辺連結グラフ: Kより小さい数の辺を取り除いても連結であるグラフ
- 二辺連結成分 (2-edge connected component): 2より小さい数(=1)の辺を取り除いても連結である部分グラフ -> 橋を含まない部分グラフ
内容
二辺連結成分は橋を含まないような部分グラフなので橋を列挙することで二辺連結成分分解ができることがわかる。
橋の検出、列挙に関しては次の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$より根方向の頂点からは$uv$を使わずに$u$に到達できるので
$uv$が橋でないことがわかる。逆に$ord[u]<low[v]$の場合は$v$から$u$より根方向に到達できないので橋であることがわかる。
一度の深さ優先探索で橋を列挙することができるので計算量は$O(n + m)$になる。
橋を列挙できれば橋の端点から橋となる辺を使わないように深さ優先探索で二辺連結成分を列挙できる。
ただ橋が存在しない場合は適当な頂点から深さ優先探索すると良い。
全体の計算量は$O(n + m)$になる。
実装は以下のようになった。
verifyにはARC039Dを用いた。submission
