\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2016年1月3日 星期日

[ Articulation Vertex ] 割點

關節點(割點)是讓一張無向圖維持連通，不可或缺的點。只要從一張無向圖上移除了關節點（以及與之相連的邊），就會讓這張圖分離成更多部分，呈現不連通的狀態。
存在一種線性算法找出一張圖所有的割點，一個dfs就能解決了

以下提供模板:

張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)