分析

求有向图的强连通分量，就是要将有向图转化成拓扑图，然后可以利用拓扑图的一些性质来方便的处理一些问题
如下图：

时间戳：$dfs$搜索过程中搜索到的顺序，即给每个点标记一个从小到大的访问顺序
$low[$ $]:$记录每个点所在强连通分量时间戳最小的点的时间戳

搜索顺序分析

$tarjan$搜索顺序和正常$dfs$搜索顺序一样，都是先将一条路径搜索到最底部再回溯处理，因此强连通分量的序号其实是在拓扑图中是从大到小来标记的。
强连通分量可以分为两类：
① 只有一个点的，如下左图，回溯的时候就只是将自己弹出，$low[u]=u$
② 一个有向环，如下右图，那么就会将整个环上的点$low[$ $]$的值都标记为最高的点的时间戳(最小)

求完强连通分量，$scc$_$cnt$从大到小就是拓扑序

因为是从下往上标拓扑序，即为拓扑序

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
        }
    }
    // 所以当遍历完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);
    }
}

$Example:$

① 受欢迎的牛
② 学校网络
求加多少边才能将有向图(可以不连通)中任意一个点都可以到达其他所有点
结论：将有向图$tarjan$缩点，然后求出入度为$0$的点$P$和出度为$0$的点$Q$，要加的边即$max(P, Q)$