【仙人掌学习笔记】一、Tarjan,从强连通分量到点双

Tarjan,一个由美国计算机科学家Robert Tarjan发明的算法。它的一个广为人知的应用是求出有向图中的强连通分量。但是这里,我将会简单的介绍一下它的另一个应用:求双连通分量。

双连通分量分为两种:点双连通分量(点双)和边双连通分量。我这里主要讲前者。

点双连通分量(下称“点双”)的定义是:若一个无向图中的去掉任意一个节点都不会改变此图的连通性,即不存在割点,则称作点双连通图;一个无向图中的每一个极大点双连通子图称作此无向图的点双连通分量。

简单来说,若一个无向图中的一个子图在任意两点间都存在两条点不重复路径,那么该子图为一个点双。再简单一点,无向图中的每一个简单环都是一个点双。

那么点双和Tarjan有何联系呢?

我们知道,Tarjan是一个基于对图的深度优先搜索(DFS)的算法,每次在搜索过程中通过记录搜索顺序(dfn)与能到达的最早的节点(low)来判断割点。我们显然可以发现对于节点u以及它能到达的节点v,有low[v]>=dfn[u]时u为割点。

然后我们就可以发现,当我们找到一个割点的时候,其实我们已经遍历完了一个点双。那么就只要用一个栈记录一下遍历过的边,然后在找到割点后不断取出栈内元素直到遇到当前边为止,我们取出来的边就是连接点双内点的边。

以下是代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
il void ClearStack(int x)
{
BCC_num++;
do{
int ed=st[top];
int v=G.e[ed^1].to;
bel[v]=BCC_num;
if(dfn[v]<dfn[rt[BCC_num]])
rt[BCC_num]=v;
}while(st[top--]!=x);
}
il void Tarjan(int x,int pre)
{
dfn[x]=low[x]=++id;
int child=0;
for(ri i=G.head[x];~i;i=G.e[i].nxt)
{
int v=G.e[i].to;
if(vis[i]||v==pre)
continue;
st[++top]=i;
vis[i]=vis[i^1]=1;
if(!dfn[v])
{
child++;
Tarjan(v,x);
low[x]=min(low[x],low[v]);
if((x==pre&&child>1)||(x!=pre&&low[v]>=dfn[x]))
ClearStack(i);
}
else
low[x]=min(low[x],dfn[v]);
}
}

我们会发现在上面这段代码中,最后得到的各点的bel值就是它所在的点双的编号(割点的bel值无意义,在求解过程中会多次变化)。

0%