推荐看吴金全的论文<有向图的强连通分量及应用> ，秒懂

在有向图 G 中，如果两个点u，v间至少存在一条路径，使得 u -> v，v -> u，则这两个点为强连通．如果有向图 G 中的任意两个点都强连通，则称 G 是一个强连通图．

Tarjan 算法

　　Tarjan 由 Robert Tarjan 发明，它的思想是：强连通分量是 DFS 树中的子树．

　　从任一节点开始进行 DFS，搜索过程中已访问的节点不再访问．搜索树中的若干棵字树构成了图的强连通分量．把当前搜索树中未处理的节点加入一个堆栈，回溯时判断栈顶到栈中的节点是否为一个强连通分量．定义 dfn(u) 为节点 u 搜索的次序编号（时间戳），low(u) 为 u 或 u 的子树能够追溯到的最早栈中节点的次序编号．由定义可得，当 dfn(u) = low(u) 时，以 u 为根的搜索子树上所有节点是一个强连通分量．

　　算法流程演示．

　　从节点１开始dfs，把遍历到的节点加入栈中．搜索到节点 u = 7 时，dfn[7] = low[7]，找到了一个强连通分量{7}．退栈到 u = v 为止，{7} 为一个强连通分量．
　　返回节点５，继续搜索５的其它邻接点６，把６加入栈，此时从６开始搜索邻接点４的时候发现４已经访问过并且还在栈中，更新 low[6] = dfn[4] = 3，接着搜索６的邻接点２的时候发现２已经访问过并且２还在栈里面，再次更新 low[6] = dfn[2] = 2，6的邻接点访问完毕，5的邻接点访问完毕，low[5] = low[6] = 2，４的邻接点访问完毕，low[4]=low[5]＝２，２的邻接点访问完毕,low[2] = 2．从4, 5, 6这四个点出发搜索完所有子节点后回来检查发现 low[4] 不等于 dfn[4]，low[5]不等于dfn[5]，low[6]不等于dfn[6]，栈中有1, 2, 4, 5, 6这五个节点．
　　返回节点２，继续搜索节点３，３入栈，从３开始搜索到１，发现１已经访问过并且仍然在栈中，此时更新low[3]=dfn[1]=1，返回到２节点，更新low[2]=low[3]=1，继续返回到节点１，没有更新low[1]，此时发现 low[1] = dfn[1]，所以将栈中节点全部出栈得到强连通分量{3, 6, 5, 4, 2, 1}．
　　至此，算法结束，得到两个强连通分量{3, 6, 5, 4, 2, 1}，{7}．
　　运行 Tarjan 算法过程中，每个顶点被访问一次，边也只被访问一次，所以时间复杂度为 O(n + e)．

const int N = 10000;
int sccno[N], dfn[N], low[N], scc_cnt, dfs_clock;
vector<int> G[N];
stack<int> s;
void dfs(int u)
{
    dfn[u] = low[u] = ++dfs_clock;
    s.push(u);
    for (auto v: G[u]) {
        if (!dfn[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (!sccno[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        scc_cnt++;
        for (;;) {
            int x = s.top();
            s.pop();
            sccno[x] = scc_cnt;
            if (x == u)
                break;
        }
    }
}
void tarjan(int n)
{
    memset(dfn, 0, sizeof(dfn));
    for (int i = 1; i <= n; i++) {
        if (!dfn(i))
            dfs(i);
    }
}