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