有向图的连通分量与强连通分量(SCC)

对于一个有向图的连通分量来说, 连通分量中任意两点u, v, 两两之间必定能互相到达, u->v, v->u. (当然一个点也是连通分量)
对于一个有向图来说, 强连通分量指的是对于有向图的一个连通分量, 加入任意一个非该连通分量的点, 连通分量将不再是连通分量, 那么我们就称其为强连通分量. 其实就是一个环你加入一个点之后, 加入点的有向边无法到环上其他个点.

有向图的强连通分量应用场景

对于一个有向图，我们可以对其强连通分量进行缩点(将强连通分量当成一个点)，从而将该有向图转化为dag，实现线性时间复杂度求最短/长路等问题.

有向图转化为拓扑图dag

几个概念

判断一个点是否在强连通分量中 -> 该点是否能走到祖先节点

• 其本身有一条后向边连向其任意祖宗节点
• 其所能到的点, 有一条后向边连向其任意祖先节点

注意: 强连通分量不一定是环！！！

如下图:

<1>tarjan算法求强连通分量 $O(n)$

时间戳: dfs遍历树时, 我们给数中每个节点按照遍历顺序一个编号, 编号即时间戳

1) 对每个点定义维护两个特性:

• dfn[u]就是以先序遍历该点的编号
• low[u]从u开始走, 所能遍历到的最小编号

2) 代码模板

void tarjan (int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ tt] = u, in_stk[u] = 1; // 注意这个地方的栈中存储的是该强连通分量中所有点和第一个不为强连通分量中的点的点集. 可能存在横叉边.

    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j]) // 未被遍历
        {
            tarjan(j); // 遍历该点
            low[u] = min(low[u], low[j]); // j能走到的祖先节点, u也一定能走到, 更新
        }
        else if(in_stk[j]) // 在当前这个强连通分量里 强连通分量中u能走到的点, 不一定是属于该SCC(因为该点不一定就能到u), 只有在栈中的才属于
            low[u] = min(low[u], dfn[j]); // 用u能到的祖先节点更新u能走到的最小编号(注意不是最小层)
    }

    if(dfn[u] == low[u]) // 第一个非强连通分量中的点, 加入该连通分量就非连通分量了, 该连通分量为强连通分量
    {
        int y;
        ++ scc_cnt;
        do
        {
            y = stk[tt -- ];
            in_stk[y] = false;
            id[y] = scc_cnt; // 强连通分量编号
        }while(y != u)
    }
}

<2>缩点建dag

for(int i = 1 ; i <= n ; i ++ )
    for(int j = h[i] ; ~j ; j = ne[j])
    {
        int k = e[j];
        if(id[i] != id[k])
            add(id[i], id[k]);
    }

<3>强连通分量编号顺序的逆序一定是拓扑序

• dfs求拓扑序

void dfs (int u)
{
    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        q[ ++ tt] = j; // 我们最先加入的点为拓扑序的尾节点, 故而q队列中的序列顺序为top序的逆序
    }   
}

1. 我们观察tarjan算法, tarjan算法是将一张连通图中的所有scc都跑一遍就都找出来
2. 我们可以发现tarjan算法的顺序与dfs求top序相同, 当我们跑到了这张图的尾节点, for循环才退出, 然后才判断该点是否为当前scc的起点并不断回溯, 并直到找到起点后在从栈中将scc弹出, 并给上标号. 所以我们说scc_cnt倒序为拓扑序. 因为最后一个scc被赋予的scc_cnt = 1.