Tarjan求解强连通分量、割点、桥
Tarjan
Robert Tarjan，是美国的计算机科学家，在1986年获得图灵奖。在LCA的blog中也有提到求解LCA的Tarjan算法。这一篇的Tarjan算法是求解强连通分量、割点和桥的。
强连通分量
有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。
求解强连通分量、割点、桥的Tarjan算法都差不多，都是通过DFS来找的。
在Tarjan算法中，有两个非常重要的变量。
dfn[i] : 表示第i个顶点在dfs中第几个访问（时间戳）
low[i] : 表示第i个顶点可以回溯到的最早访问的顶点
可能这样说难以理解，一会看图解和代码就理解了。
在求解强连通分量时，为了知道一个强连通分量有哪些顶点，还需要用到stack。
Tarjan求解强连通分量的伪代码如下
low[u] = dfn[u] = ++ind;
ins[u] = 1;
stack.push(i);
for v in <u, v>:
if(v is not visited):
Tarjan(v)
low[u] = min(low[u], low[v]);
else if(v in stack):
low[u] = min(low[u], dfn[v]);
if(low[u] == dfn[u]):
int p;
cnt++;
do:
p = stack.top;
stack.pop;
ins[p] = 0;
belong[p] = cnt;
while(p != u)
图解来辽，就用下面这个图来做例子吧
然后根据DFS，到下图
这时候访问到顶点5，已经没法继续DFS了，并且low[5] = dfn[5]，说明存在强连通分量。把栈中的元素依次出栈，直到遇到了顶点5。这里只出栈了顶点5，说明顶点5单独成为一个强连通分量。
回退到顶点3
这时候和刚刚的情况一样，顶点3单独成为一个强连通分量。
回退到顶点2，DFS遍历顶点4.
这时候顶点4发现顶点1已经遍历过了，所以更新顶点4的low为1.
回退到顶点2，更新顶点2的low
回退到顶点1，发现low[1] = dfn[1]，将栈中的元素出栈，知道遇到1。这时候顶点1、 2、 4成为一个强连通分量。
到这里整个算法就结束了～
模板如下：
vector<int> g[maxn];
int low[maxn], dfn[maxn], sta[maxn], ins[maxn], belong[maxn];
int cnt, ind, tot; //cnt：强连通分量的数量， ind：时间戳， tot：sta的top
void init()
{
memset(ins, 0, sizeof(ins));
memset(belong, 0, sizeof(belong));
memset(dfn, 0, sizeof(dfn));
cnt = ind = tot = 0;
}
void Tarjan(int u)
{
low[u] = dfn[u] = ++ind;
ins[u] = 1;
sta[++tot] = u;
for(int i=0;i<g[u].size();i++)
{
int v = g[u][i];
if(!dfn[v])
{
Tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(ins[v])
low[u] = min(low[u], dfn[v]);
}
int p;
if(low[u] == dfn[u])
{
++cnt;
do
{
p = sta[tot--];
belong[p] = cnt;
ins[p] = 0;
}while(p != u);
}
}
割点
在一个无向图中，如果删除一个顶点及与它相关联的边之后，图的连通分量增多了，则称这一个点为割点。
对于根节点来说，只要它至少有两颗子树，那么根节点一定是割点。对于其它顶点来说则麻烦一些。
回想一下Tarjan算法中low的意义，表示该顶点能够回溯到最早访问的顶点的序号。对于一个顶点来说，在它之前访问的一个顶点是该顶点的父亲，在它父亲之前的是它的祖先，若该顶点能够不通过父亲就回溯到祖先的话，那么说明该顶点的父亲不是割点。所以，若一个顶点的所有儿子都能够不通过它自己就能回溯到祖先顶点，则该顶点不是割点，否则就是割点。
所以对于边<u, v>来说，若low[v] >= dfn[u]，则u是割点。
对于上图来说，顶点2和3都是割点。
模板如下
vector<int> g[maxn];
// iscut[i]: 若顶点i是割点，则为1，反之为0
int low[maxn], dfn[maxn], iscut[maxn];
int ind;
void init()
{
memset(dfn, 0, sizeof(dfn));
memset(iscut, 0, sizeof(iscut));
ind = 0;
}
// pa为u的父节点，初始时Tarjan(i, i)
void Tarjan(int u, int pa)
{
int cnt = 0; //用来记录子树的数量
low[u] = dfn[u] = ++ind;
for(int i=0;i<g[u].size();i++)
{
int v = g[u][i];
if(!dfn[v])
{
Tarjan(v, u);
low[u] = min(low[u], low[v]);
// 若low[v]>=dfn[u]，并且u不是根节点，则u是割点
if(low[v] >= dfn[u] && pa!=u)
iscut[u] = 1;
// 若u是根节点，则cnt++
if(u == pa)
cnt++;
}
else if(v != pa) //若v不等于父节点
low[u] = min(low[u], dfn[v]);
}
if(cnt>=2 && u==pa) //根节点子树数量大于等于2，则为割点
iscut[u] = 1;
}
桥
桥也叫割边，对于边e来说，若去掉了e，图的连通分量增多了，则说明e为桥。
找割边和找割点很像。对于边<u, v>来说，若low[v] > dfn[u]， 则<u, v>是桥。
所以对于上图来说，边<2, 3>和<3, 5>都是桥。
模板：
// 用链式前向星来存储边
struct Edge
{
// iscut表示是否为桥
int to, next, iscut;
}e[maxn*maxn*2];
int head[maxn], low[maxn], dfn[maxn];
int ind, tot; // tot是边的数量
void init()
{
memset(head, -1, sizeof(head));
memset(dfn, 0, sizeof(dfn));
ind = tot = 0;
}
void addedge(int u, int v)
{
e[tot].to = v;
e[tot].next = head[u];
e[tot].iscut = 0;
head[u] = tot++;
}
void Tarjan(int u, int pa)
{
low[u] = dfn[u] = ++ind;
for(int i=head[u]; ~i; i = e[i].next)
{
int v = e[i].to;
if(v == pa) continue;
if(!dfn[v])
{
Tarjan(v, u);
low[u] = min(low[u], low[v]);
// 是桥
if(low[v] > dfn[u])
{
// 因为加边时，是加双向边的，所以编号0和1, 2和3...等是一对边，i^1就能取到另一条边，可自行测试
e[i].iscut = e[i^1].iscut = 1;
}
}
else
{
low[u] = min(low[u], dfn[v]);
}
}
}
END
Tarjan还可以用来缩点，emmm咕咕咕。 溜～