有向图的强联通分量

Tarjan算法

原理

Tarjan算法通过对于有向图的dfs，将图看成一颗树的形式，并且把树中的边分为四类：

1. 树枝边：树中从a到b在dfs中相邻的边。
2. 前向边：树中在dfs过程中，从祖先某个节点连接到未来某个节点的边。其中树枝边是前向边的特例。
3. 后向边：从当前dfs遍历的节点连接回dfs路径上某个点的边。
4. 横插边：从当前dfs遍历的节点连接回某个祖先节点的边。

在遍历的过程中，用dfn数组记录第一次遍历到时的时间戳，用low数组记录当前节点可以走到的最早的祖先节点的时间戳，这样如果dfn[u] == low[u]表示当前节点是遍历的当前强联通分量的最早的节点，因此将栈中记录的所有点进行回溯，放到同一个联通分量中。

一般来说Tarjan算法求完强联通分量之后，都会进行缩点操作，然后进行拓扑图上的拓扑顺序的遍历。当求完所有强联通分量之后，scc_cnt递减的顺序就是当前拓扑图的拓扑遍历顺序，不用再写拓扑排序进行遍历。

模板

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;

      stk[ ++ top ] = u, in_stk[u] = true;

    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]);
        }
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        int y;
        ++ scc_cnt;
        do {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;
            sz[scc_cnt] ++ ;
        }
    }
}

例题

AW.1174 最受欢迎的牛（中等）