Tarjan算法介绍

Tarjan算法

Tarjan算法是用来求有向图的强连通分量的算法，可以用来解决割点，割边问题，但它们各自的代码都有一些区别。

Tarjan算法是利用dfs来进行的，它的访问次序可以组成一颗搜索树，每一个连通分量是一个子树。
引入两个数组：

dfn[]: dfn[i]表示结点i被访问的时间戳(或者先后次序)
low[]: low[u]为u或u的子树中能通过非父子边追溯到的最早的节点

步骤：
1.若dfs[i]==0，即结点i从未被访问过，那么设置值dfn[i] = low[i] = 0，将i如栈，标记vis[i] = 1.
2.遍历结点i指向的结点j，若j没有被访问过(dfn[j]==0)，访问j(回到步骤1)，更新值low[i] = min(low[i], low[j])；若结点j被访问过(dfn[j]有值)，且还在栈中(vis[j]==1)，那么更新值low[i] = min(low[i], dfn[j]).
3.遍历完所有i指向的结点后，若有dfn[i]==low[i]，那么栈里面从栈顶到结点i之间的值构成一个强连通分量。连续出栈至i(结点i也出栈)，即low[]值相同的结点构成一个强连通分量。

代码：

void Tarjan(int u){
    dfn[u] = low[u] = ++num;
    vis[u] = 1;
    sta.push(i);
    for (int i=head[u]; i; i=e[i].next){
        if (!dfn[e[i].to]){
            Tarjan(e[i].to);
            low[u] = min(low[u], low[e[i].to]);
        }else if (vis[e[i].to])
            low[u] = min(low[u], dfn[e[i].to]);
    }
    if (low[u]==dfn[u]){
        while (sta.top()!=u){
            vis[sta.top()] = 0;
            low[sta.top()] = low[u];
            sta.pop();
        }
        vis[sta.top()] = 0;
        sta.pop();
    }
    return;
}