Low-Link
説明
橋や関節点を効率よく求める際に有効なアルゴリズム。
グラフをDFSして, $\mathrm{ord}[idx] := $ DFS で頂点に訪れた順番, $\mathrm{low}[idx] := $ 頂点 $idx$ からDFS木の葉方向の辺を $0$ 回以上, 後対辺を $1$ 回以下通って行ける頂点の $ord$ の最小値 を各頂点について求める。
使い方
Union-Find が必要
計算量
$O(E + V)$
$V$: 頂点数, $E$: 辺数
実装例
橋や関節点を効率よく求める際に有効なアルゴリズム。
グラフをDFSして, $\mathrm{ord}[idx] := $ DFS で頂点に訪れた順番, $\mathrm{low}[idx] := $ 頂点 $idx$ からDFS木の葉方向の辺を $0$ 回以上, 後対辺を $1$ 回以下通って行ける頂点の $ord$ の最小値 を各頂点について求める。
Union-Find が必要
$O(E + V)$
$V$: 頂点数, $E$: 辺数