\( \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月27日 星期三

[ Biconnected Component ] 雙連通分量(BCC)

一張無向圖上,不會產生割點的連通分量,稱作「雙連通分量」。一張無向圖的雙連通分量們,通常會互相重疊,重疊的部分都是原圖的割點。
可以利用堆疊+tarjan算法快速地找出那些點是割點和雙連通分量
以下提供模板:

沒有留言:

張貼留言