hdu1269 迷宮城堡，有向圖的強連通分量 ， Tarjan算法

hdu1269 迷宮城堡，有向圖的強連通分量 ， Tarjan算法

hdu1269 迷宮城堡

驗證給出的有向圖是不是強連通圖。。。

Tarjan算法板子題

Tarjan算法的基礎是DFS，對於每個節點、每條邊都搜索一次，時間復雜度為O(V+E)。

算法步驟：

1、搜索到某一個點時，將該點的Low值標上時間戳，然後將自己作為所在強連通分量的根節點（就是賦值Dfn=Low=time）
2、將該點壓入棧。
3、當點p有與點p’相連時，如果此時p’不在棧中，p的low值為兩點的low值中較小的一個。
4、當點p有與點p’相連時，如果此時p’在棧中，p的low值為p的low值和p’的dfn值中較小的一個。
注釋：因為此時在棧中，所以p‘的強連通分量的父節點需要重新指向（感覺學過並查集理解得更快一些） 。

5、當子樹全部遍歷完畢，將low值等於dfn值，則將它以及在它之上的元素彈出棧。這些出棧的元素組成一個強連通分量。
　 這裡的子樹全部遍歷完畢不是指的所有子節點遍歷完畢，而是一個強連通分量的搜索樹遍歷完畢。
6、選擇一個未搜索的節點作為根節點進行搜索，直到所有節點搜索完畢為止。

#include
#include
#include
#include
#include
using namespace std;

const int maxn = 100000 + 10;

vector G[maxn];
int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;
stack S;

void dfs(int u){
    pre[u] = lowlink[u] = ++ dfs_clock;
    S.push(u);
    for(int i=0; i