由于刷CCF时遇到了类似的问题，最近学习了下Tarjan求强连通的算法。

　　基本的原理：通过Dfs遍历点，某点在拓展后仍能回归到自己，则该点处在图的一个强连通分量上。

　　基本工具：

1. int dfn[i]：记录i在dfs中第一次被访问到的次序（时间序，只增不减）。
2. int low[i]：i所能到达的最早的点的次序，也是最小子树的根。
3. bool in_stack[i]：i是否在栈中。
4. int mystack[i]：手写的栈，用来存储dfs过程中遍历到的点（直接用stl的栈也是一样的）。
5. int scc_cnt：强连通分量的数量。
6. int num[id]：id强连通分量中的点的个数。
7. int belong[i]：i所属的强连通分量的编号。

　　要用到的东西挺多，我刚开始看时也觉得挺吓人的~

　　过程简述：

　　每次将一个新节点栈并且标记在栈中，该节点由出度则继续沿着该节点拓展到底。到底后逐个回溯（dfs的特点），每次返回时都比较本点与上一点的low值（所能抵达的最早的点的时间序），取其中的最小值。若发现点u的dfn[u] == low[u]，则u为以个强连通分量的根节点，那么从栈顶（最后进栈的点）到u（包括u）的点构成一个强连通分量，将其全部出栈。继续回溯。。。

模板先来：

const int maxv = 1e4 + 4, maxe = 5 * 1e4 + 4;struct Edge{    int to, next;}e[maxe];int head[maxv], cnte;inline void add_edge(const int& from, const int& to){    cnte += 1;    e[cnte].to = to, e[cnte].next = head[from];    head[from] = cnte;    return;}int n, m;int dfn[maxv], low[maxv], index, scc_cnt;int num[maxv];int mystack[maxv], top;bool in_stack[maxv];int belong[maxv];void tarjan(const int& q){    dfn[q] = low[q] = ++index;    mystack[++top] = q;        in_stack[q] = true;    for(int i=head[q]; i; i = e[i].next){        if(!dfn[e[i].to]){            tarjan(e[i].to);            low[q] = min(low[q], low[e[i].to]);        }else if(in_stack[e[i].to]){            low[q] = min(low[q], dfn[e[i].to]);        }else             continue;    }    int v = 0;    if(dfn[q] == low[q]){    //找到强连通分量子树上的根节点        scc_cnt += 1;        do{
   //退栈            num[scc_cnt] += 1;    //统计强连通分量上点的数量            v = mystack[top--];            belong[v] = scc_cnt;            in_stack[v] = false;        }while(q != v);    //q == v 时，q（v）已经退栈    }    return;}