説明
二辺連結成分分解とも。二重辺連結成分(2-edge connected component) とは, $1$ 個の辺を取り除いても連結である部分グラフである。つまり橋を含まないような部分グラフなので, 橋を列挙することで二重辺連結成分を列挙できる。
計算量
実装例
依存ライブラリ LowLink
- TwoEdgeConnectedComponents($g$):= グラフ $g$ で初期化する。
- build($t$):= 二重辺連結成分分解をする。$t$ には二重辺連結成分ごとに縮約したグラフが格納される(橋のみからなるグラフ)。
- [$k$]:= 頂点 $k$ が属する二重辺連結成分の番号を返す。
検証
AtCoder Regular Contest 039 - D 旅行会社高橋君