Tarjan算法 边双和点双

边双连通分量

边双连通图:如果一个无向连通图中,没有割边,那么这个无向连通图就是一个边双连通图。

一个无向图的极大边双连通子图就是它的其中一个边双连通分量。
我们要解释下这里“极大”的概念:如果一个连通子图$G1$是边双,那么不存在一个原图的子图$G2$既满足$G1\in G2$又满足$G2是边双$。

边双的“极大”不是指整个图范围内的最大,而是所有把某一个边双作为子图的所有连通子图的范围内而谈的。

求法

tarjan求出所有割边,然后把割边去掉,就是一个个边双连通分量了。
然后只要去掉割边进行dfs染色就行了。

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
int low[maxn],dfn[maxn],cnt=0;
bool bridge[maxm<<1];
void tarjan(int x,int in_edge){
dfn[x]=low[x]=++cnt;
for(int i=head[x];i+1;i=a[i].next){
int y=a[i].y;
if(!dfn[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(low[y]>low[x])bridge[i]=bridge[i^1]=true;
}
else if(i!=(in_edge^1))
low[x]=min(low[x],dfn[y]);
}
}
int block[maxn],dcc=0;
void dfs(int x,int color){
block[x]=color;
for(int i=head[x];i+1;i=a[i].next){
int y=a[i].y;
if(bridge[i])continue;
if(!block[y])dfs(y,color);
}
}
void get_edccs(){
for(int i=1;i<=n;i++)
if(!block[i])
dfs(i,++dcc);
}

边双缩点

只要把所有的边双作为点,然后把割边保留下来建新树就行了。

点双连通分量

参照边双的定义,我们可以定义出点双:
在一个无向连通图中,如果没有割点,那么它是点双连通图。
如果只有两个点,那么也是点双。
一个无向图中的极大点双连通子图就是点双连通分量。
这里的“极大”同上。
我们可以发现,一个割点可以属于多个点双。但是一条割边不属于任何边双。

求法(如果不理解可以手推一组小数据)

开一个栈,tarjan递归访问到某个点的时候入栈,然后每次经过一条边$(x,y)$而且x满足$low[y]>=dfn[x]$的时候不管x是不是割点,都把栈里的元素一一弹出,直到把y弹出,所有弹出的点,再加上x,构成一个点双。

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
void tarjan(int x,int in_edge){
low[x]=dfn[x]=++cnt;sta[++t]=x;
for(int i=head[x];i+1;i=a[i].next){
int y=a[i].y;
if(!dfn[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
int u;
dcc++;size=0;
vdcc.clear();
do{
u=sta[t--];
block[u]=dcc;
size++;
vdcc.push_back(u);
}while(u!=y);
block[x]=dcc;
vdcc.push_back(x);
size++;
work();
}
}
else low[x]=min(low[x],dfn[y]);
}
}

点双缩点

每一个割点建点,每一个点双建点,然后根据从属关系连边。
这里我们画个图吧
这里写图片描述

文章目录
  1. 1. 边双连通分量
    1. 1.1. 求法
    2. 1.2. 边双缩点
  2. 2. 点双连通分量
    1. 2.1. 求法(如果不理解可以手推一组小数据)
    2. 2.2. 点双缩点