関節点(Articulation-Points)
説明
low-link の結果を用いて関節点を効率よく求める。
DFS木の木の根については, 子が $2$ つ以上なら関節点, それ以外の頂点 $v$ については, $\mathrm{ord}[u] \le \mathrm{low}[v]$ となる $v$ の子 $u$ が存在するとき関節点となる。
使い方
Low-Link が必要
計算量
$O(V + E)$
$V$: 頂点数, $E$: 辺数
実装例
low-link の結果を用いて関節点を効率よく求める。
DFS木の木の根については, 子が $2$ つ以上なら関節点, それ以外の頂点 $v$ については, $\mathrm{ord}[u] \le \mathrm{low}[v]$ となる $v$ の子 $u$ が存在するとき関節点となる。
Low-Link が必要
$O(V + E)$
$V$: 頂点数, $E$: 辺数