有向图
连通分量:对于分量中任意两点u,v 必然可以从u走到v 且从v走到u
强连通分量:极大连通分量
有向图   →   有向无环图(DAG)
        缩点(将所有连通分量缩成一个点)
缩点举例:
   o→o→o→o
     ↑ ↓
   o→o→o→o
中间的环缩成一个点
o     o
  ↘ ↗
   o
  ↗ ↘ 
o     o
应用:
求最短/最长路 递推

求强连通分量:dfs
1 树枝边(x,y)
        o
       / \
      o   o
     /   / \
    o   o   o
2 前向边(x,y)
        o
       / \
      o   x
     /  ↙ \
    o   y   o
3 后向边
        o
       / \
      o   y
     /  ↗ \
    o   x   o
4横插边(往已经搜过的路径上的点继续深搜)
因为我们是从左往右搜的 所以一般是x左边分支上的点
        o
       / \
      o   o
     /   / \
    y ← x   o
如果往x右边边分支上的点搜 则属于树枝边

强连通分量：
情况1：
    x存在后向边指向祖先结点y 直接构成环
        o
       / \
      o   y
     /  ↗/\
    o   x   o
情况2：
    x存在横插边指向的点y有指向x和y的公共祖先节点及以上的点的边
    再通过根节点往下走到x间接构成环
        o
   ↗  / \
  ↗  o   o
 ↗  /   / \
    y ← x   o

Tarjan 算法求强连通分量
引入 时间戳(按dfs 回溯的顺序标记)
        1
   ↗  / \
  ↗  2   4  
 ↗  /   / \
    3 ← 5   6
标记上时间后:
dfn[u]dfs遍历到u的时间(如上图中的数字)
low[u]从u开始走所能遍历到的最小时间戳(上图中1,2,3,4,5都是一个环/强连通分量中的
                                    即dfn[1]=low[1]=low[2]=low[3]=low[4]=low[5])
    --即u如果在强连通分量,其所指向的层数最高的点

u是其所在的强连通分量的最高点 (上图中dfn[1]=low[1] dfn[6]=low[6])
           <=> 
     dfn[u] == low[u]

树枝边(x,y) 中dfn[y]>dfn[x] low[u]>dfn[u]
前向边(x,y) 中dfn[y]>dfn[x] low[u]>dfn[u]
后向边(x,y) 中dfn[x]>dfn[y] 后向边的终点dfn[u] == low[u]
横插边(x,y) 中dfn[x]>dfn[y] 

缩点
for i=1;i<=n;i++
 for i的所有邻点j
   if i和j不在同一scc中:
    加一条新边id[i]→id[j]

缩点操作后变成有向无环图
就能做topo排序了(此时连通分量编号id[]递减的顺序就是topo序了)
因为我们++scc_cnt是在dfs完节点i的子节点j后才判断low[u]==dfn[u]后才加的
        那么子节点j如果是强连通分量 scc_idx[j]一定小于scc_idx[i]

板子+详解

void tarjan(int u)
{
    //u的时间戳
    dfn[u] = low[u] = ++timestamp;
    //把当前点加到栈中  当前点在栈中
    stk[++top] = u,in_stk[u] = true;

    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])//j点未被遍历过
        {
            tarjan(j);//继续dfs 遍历j
            //j也许存在反向边到达比u还高的层,所以用j能到的最小dfn序(最高点)更新u能达到的(最小dfn序)最高点
            low[u] = min(low[u],low[j]);
        }
        //j点在栈中  说明还没出栈 是dfs序比当前点u小的
        //则其 1要么是横插边(左边分支的点)
        //         o
        //        / \
        //       j ← u    
        //     2要么是u的祖宗节点
        //         j
        //      ↗/ 
        //       u    
        //    两种情况u的dfs序都比j大 所以用dfn[j]更新low[u]
        else if(in_stk[j])
        {
            low[u] = min(low[u],dfn[j]);//直接用j的时间戳更新u
        }
        //栈代表当前未被搜完的强连通分量的所有点
    }
    // ⭐
    // 解释一下为什么tarjan完是逆dfs序
    // 假设这里是最高的根节点fa
    // 上面几行中 fa的儿子节点j都已经在它们的递归中走完了下面9行代码
    // 其中就包括 ++scc_cnt 
    // 即递归回溯到高层节点的时候 子节点的scc都求完了
    // 节点越高 scc_id越大
    // 在我们后面想求链路dp的时候又得从更高层往下
    // 所以得for(int i=scc_cnt(根节点所在的scc);i;i--)开始

    // 所以当遍历完u的所有能到的点后 发现u最高能到的点是自己
    // 1 则u为强连通分量中的最高点,则以u为起点往下把该强连通分量所有节点都找出来
    // 2 要么它就没有环,就是一个正常的往下的点
    if(dfn[u]==low[u])
    {
        int y;
        ++scc_cnt;//强连通分量总数+1
        do
        {
            y = stk[top--];//取栈顶元素y
            in_stk[y] = false;//则y不再在栈中
            id[y] = scc_cnt;
            Size[scc_cnt] ++;//第scc_cnt个连通块点数+1
        }while(y!=u);
        //1 因为栈中越高的元素的dfs序越大,那么我们只需要把dfs序比u大的这些pop到u
        //即因为最终会从下至上回到u 所以当y==u     
        //则说明点u所在的所有强连通分量都标记了id
        //           →  u
        //          /  /
        //         /  ne1
        //         ← ne2
        //      因为ne2会在u能到的dfs序里最大的,也就是此时的栈顶
        //      那么我们就逐一pop出ne2和ne1
        //2 要么它就是一个没有环的点 则该点单点成一个连通分量
    }
}

鸣谢大佬，总结的生动，直接copy过来了
原贴 仅存老实人

一些补充
但是这里有些东西要补充一下，第187行的代码

low[u] = min(low[u],dfn[j]);

中，dfn[j]换成low[j]也是对的，因为u一定有办法到j，所以low[u]一定是可以被low[j]所更新的。
但是这样low的定义就会被破坏了
详见 此处