双连通分量

两只$\mathbf{Tarjan}$,两只$\mathbf{Tarjan}$,跑得快,跑得快……

一 概念

1 基本定义

无向图的双连通有两种情况:点-双连通 与 边-双连通。

  • 点-双连通:若一个无向图中的去掉任意一个节点,都不会改变此图的连通性,即不存在割顶,则称作点-双连通图。 —— Baidu
  • 边-双连通:若一个无向图中的去掉任意一条边,都不会改变此图的连通性,即不存在桥,则称作边-双连通图。 —— Baidu

类似与有向图的强连通分量,无向图的 点-双连通 的极大子图被称作该图的双连通分量(BiConnected Component,BCC)。而无向图的 边-双连通 的极大子图被称作该图的边-双连通分量(Edge-BiConnected Component,EBCC)。

上述还涉及到了两个概念,割顶,定义如下:

  • 对于一张无向图,若删去一个端点后,产生了新的连通块,则称这个端点为割顶(也称割点)。
  • 对于一张无向图,若删去一条边后,产生了新的连通块,则称这条边为桥(也称割边)。

不难发现:割顶决定了点-双连通,而桥决定了边-双连通。

对于一张无向图,割顶(桥)可能不存在,也可能不仅一个。

2 图示

bcc1

如上图,节点$4$是割顶,边$(4,6)$是桥。
图中点-双连通子图有${1,2,4}$,${1,3,4,5}$等,但BCC只有${1,2,3,4,5}$和${6}$。
类似的,边-双连通子图有${1,2,4}$等,但EBCC只有${1,2,3,4,5}$和${6}$。


二 割顶

在求解BCC之前,先来学习割顶的必备知识。

注:因为 桥和边-双连通 与 点-双连通 有许多相似之处,故不重点说明。
以下所有 “双连通/双连通子图/双连通分量/BCC” 等均指 “点-双连通”。

1 dfs树

dfs树的基本内容在SCC算法分析中已经讲过,这里不再过多重复,只对部分概念做必要说明。

  • 树边:dfs所经过的边
  • 返祖边:连接子节点与它的祖先节点的边,本质上与树边无异

注意:无向图的dfs树上不存在横叉边。

可以绘制出上图的dfs树:
bcc6

2 定理

我们先来推导一下割顶的基本判定方法。

猜想:

  • 在一个无向图中,若$u$是割顶,当且仅当$u$存在一个子节点$v$,使得子树$v$内没有边返回$u$的祖先。

画出图来就长这样:
bcc4

看上去很对,但是有疏漏。

根节点很特殊。一定没有返祖边指向根的祖先,因为根没有祖先。但是仅当根由两棵及以上的子树时,根才是割点,否则删去它并不影响图的连通。
所以需要特判根。

2-1 割顶的判定定理

  1. 根节点是割顶,当且仅当在dfs树上它有两个及以上的子节点。
  2. 非根节点$u$是割顶,当且仅当在dfs树上$u$存在一个子节点$v$,使得子树$v$内没有返祖边返回$u$的祖先。

简单证明:

  1. 此时删去根节点会让它的各个子树互不连通,因为不存在横叉边。
  2. 此时删去$u$,会使得子树$v$中的节点“独立”出来,形成新的连通块。

2-2 桥的判定定理

与上面的类似。

  • 对于任意节点$u$,若$u$存在一个子节点$v$,使得子树$v$内没有返祖边返回**$u$及$u$的祖先**,则边$(u,v)$是桥。

图示如下:
bcc3

证明其实挺好想:删掉这条边会孤立子树$v$。

3 算法

该算法由Robert Tarjan提出(又是他)。

3-1 思路

设节点$u$被dfs到的次序号是$dfn[u]$,从它能到达的祖先的最小次序号是$low[u]$,那么定理中的第二条就变成了:

  • 找一个节点$u$,使得$low[v] \geqslant dfn[u] | (u,v)\in E$,则判定$u$是割顶。

同理,桥的判定定理可以表示为:

  • 找一个节点$u$,使得$low[v] > dfn[u] | (u,v)\in E$,则判定无向边$(u,v)$是桥。

于是可以在dfs一张无向图的时候求解。

3-2 流程

该算法主要有以下四步:

  1. dfs整个图。
  2. 对于每个非根节点,使用子节点的$low$值更新当前节点的$low$值。
  3. 访问该节点出发的所有返祖边,并用这条边指向的祖先的$dfn$值更新当前节点的$low$值。注意一定是$dfn$值,下面会讲。
  4. 判定是否是割顶(用到上面的不等式)。

对于1-2中的图,可以得到如下的一张dfs树(桥和割顶都已经标出)。
bcc2
发现存在$low[6]\geqslant dfn[4]$,故判定$4$是割顶。

小问题:为什么一定是dfn值?

看下面的图。
bcc5

此时使用$low[u]$更新$low[v]$,实际上走了两条返祖边。则会判定$u$不是割顶,但实际上它是。

3-3 代码

割顶的求解如下:

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
const int CP=1e3+3;
const int CE=CP*CP;

//边表
class fs{
public:
int to,nxt;
}E[CE];
int hd[CP],cnt=0;
void add(int x,int y)
{
E[++cnt].to=y;
E[cnt].nxt=hd[x];
hd[x]=cnt;
}

//cut
int dfn[CP],low[CP];
int idx=0;

bool iscut[CP]; //是否是割顶

void tarjan(int cur,int prv)
{
int child = 0; //孩子数,用于根的特判

dfn[cur] = low[cur] = ++idx; //设置初始值

for(int k=hd[cur]; k; k=E[k].nxt)
{
int to=E[k].to;

if(!dfn[to]) //是树边
{
child++;
tarjan(to,cur); //向下搜索

low[cur] = min(low[cur], low[to]); //更新

if(low[to] >= dfn[cur]) //用儿子来判定
iscut[cur]=true;
}
else if(to != prv) //是返祖边
low[cur] = min(low[cur], dfn[to]); //更新
}

if(!prv && child==1) //处理根
iscut[cur]=false;
}

void bcc() //主求解函数
{
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i,0);
}

桥的求解如下:

因为边表没法有效地一次性保存双向边。所以边的下标从$1$开始,使得$k \text{ xor } 1$就是$k$的反向边。($k$与$k \text{ xor } 1$共同组成一条无向边)。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
const int CP=1e3+3;
const int CE=CP*CP;

//边表
class fs{
public:
int to,nxt;
}E[CE];
int hd[CP],cnt=1; //从1开始
void add(int x,int y)
{
E[++cnt].to=y;
E[cnt].nxt=hd[x];
hd[x]=cnt;
}

//bridge
int dfn[CP],low[CP];
int idx=0;

bool isbri[CE]; //是否是桥

void tarjan(int cur,int prv)
{
dfn[cur] = low[cur] = ++idx;

for(int k=hd[cur]; k; k=E[k].nxt)
{
int to=E[k].to;

if(!dfn[to])
{
tarjan(to,cur); //向下搜索

low[cur] = min(low[cur], low[to]);

if(low[to] > dfn[cur]) //判定
isbri[k] = isbri[k^1] = true;
}
else if(to != prv)
low[cur] = min(low[cur], dfn[to]);
}
}

void ebcc() //主求解函数
{
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i,0);
}

三 算法实现

1 BCC

学会了求解割顶,求出BCC就再容易不过了。

维护一个栈,栈内保存每一次走过的边(一定保存边,因为两个不同的双连通子图可能有交点,但一定没有交边)。每当发现割顶时,出栈,直到发现当前出栈的边恰好是连接割顶与判定它的子节点的边。则出栈的所有边同属一个双连通子图,这些边的端点也同属一个双连通子图。

代码如下:
因为回溯到根的时候,剩余栈内元素一定是一个双连通子图,故先出栈再特判根。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
const int CP=1e3+3;
const int CE=CP*CP;

//边表
class fs{
public:
int from,to,nxt;
}E[CE];
int hd[CP],cnt=0;
void add(int x,int y)
{
E[++cnt].from=x;
E[cnt].to=y;
E[cnt].nxt=hd[x];
hd[x]=cnt;
}

//bcc
int dfn[CP],low[CP];
int idx=0;

int bel[CP],bcnt=0; //每个点所属的bcc编号,为-1则表示该点是割顶(割顶同时属于两个bcc,所以它的bel无意义)
int stack[CE],top=0;

void tarjan(int cur,int prv)
{
int child = 0;

dfn[cur] = low[cur] = ++idx;

for(int k=hd[cur]; k; k=E[k].nxt)
{
int to=E[k].to;

if(!dfn[to])
{
child++;
stack[++top]=k; //入栈
tarjan(to,cur); //向下搜索

low[cur] = min(low[cur], low[to]);

if(low[to] >= dfn[cur]) //是割顶
{
int pos;
++bcnt;
while(true)
{
pos=stack[top--]; //出栈
bel[E[pos].from] = bel[E[pos].to] = bcnt;
if(E[pos].from==cur && E[pos].to==to) //发现当前的树边
break;
}
bel[cur] = -1; //标记割顶
}
}
else if(to != prv)
low[cur] = min(low[cur], dfn[to]);
}

if(!prv && child==1) //处理根
bel[cur] = bcnt;
}

void bcc() //主求解函数
{
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i,0);
}

2 EBCC

EBCC可以用更简单的两遍dfs求出:

第一遍dfs在图上删去所有的桥。第二遍dfs求出这之后所有的连通块。
那么每个连通块都是一个边-双连通子图。


四 BCC可以解决什么样的问题?

噫,好了,我中了,我们已经学会了BCC。
但是BCC可以用来求解什么样的问题呢?

在这里梳理一下BCC的主要性质:

  1. 一个BCC一定是若干个简单环(环上的边数等于点数)的并。求出BCC的主要目的就是求出图上的若干环。
  2. 根据双连通(也是环的性质)可知:同一双连通子图中的点一定有至少两条路径可达。
  3. 两个不同的双连通子图的交点一定是该图的割顶,或这个点不存在。
作者

ce-amtic

发布于

2019-03-08

更新于

2021-01-04

许可协议

CC BY-NC-SA 4.0

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×