浅谈Tarjan算法

本篇随笔简单讲解一下Tarjan缩点算法。Tarjan算法支持很多东西，什么桥割点之类的，这里只介绍缩点的那个Tarjan。

---

一、前置知识和概念

Tarjan缩点的学名其实是Tarjan算法求强连通分量。那么介绍这些概念：

强连通：如果两个顶点可以相互通达，则称两个顶点 强连通(strongly connected)。如果有向图G的每两个顶点都 强连通，称G是一个强连通图。非 强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。

来个经典图，大多数人讲Tarjan都会用到的图：

在这张图中，1234就是个强连通分量。

---

二、Tarjan算法的原理

很多博客上都只着重讲了Tarjan的实现，并没有太过于讲解其原理上的东西。那我来补充一下，因为我水平实在是有限，所以如果有的说的不对的敬请指正。

强连通分量是啥啊，那不是两两可达么。

既然可达，那对其进行遍历的时候肯定会重复通过啊。那中间它怎么来的就是和它在一个强连通分量里的呗。

那么我们用DFS+一个栈来维护这个过程。

两个数组：一个dfn是时间戳。如果不知道时间戳是啥，戳这里：时间戳，一个low表示目前在栈里的所有节点中时间戳最小的时间戳，换句话说，是i或i的子树能够追溯到的最早的栈中节点的时间戳。

整个算法的执行过程是对整张图进行深度优先遍历的过程。当回溯时dfn[x]==low[x]时，以之为根的子搜索树的所有节点可以被构成一个强连通分量。

比如上面的那张图，我们可以手动模拟这个过程。

---

三、Tarjan算法的代码实现

代码：

void tarjan(int x)
{
    dfn[x]=low[x]=++cnt;
    st[++top]=x;
    v[x]=1;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(v[y])
            low[x]=min(low[y]);
    }
    if(low[x]==dfn[x])
    {
        int now;
        do
        {
            now=st[top--];
            v[now]=0;
        }while(now!=x);
    }
}