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

[ Strongly Connected Component - Tarjan & Kosaraju ] 強連通分量的兩種做法(dfs)

一張有向圖，找到所有的 Strongly Connected Component ；亦可進一步收縮所有的 SCC 、收縮所有的環，讓原圖變成 DAG 。

方法1-Tarjan法
跟BCC差不多，直接提供模板:

方法2-Kosaraju
對圖做一次DFS，求他的時間戳，再把圖反向，逆著時間戳進行第二次DFS，所遍歷的點就會是同一個SCC，記得不要走重複的點
以下提供模板:

用法:

張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)