二重辺連結成分分解(Biconnected-Components)
説明
二重辺連結成分分解する。副作用として橋を返す。
辺 $(u, v)$ は $\mathrm{ord}[u] \lt \mathrm{low}[v]$ のとき橋となる。
使い方
Low-Link が必要
計算量
$O(V + E)$
実装例
二重辺連結成分分解する。副作用として橋を返す。
辺 $(u, v)$ は $\mathrm{ord}[u] \lt \mathrm{low}[v]$ のとき橋となる。
Low-Link が必要
$O(V + E)$