双连通分量
[TOC]
介绍
若一个无向连通图不存在割点，则称它为“点双连通图”。若一个无向连通图不存在割边，则称它为“边双连通图”。 无向图的极大点双连通子图称为“点双连通分量”，简记为“v-DCC”。无向连通图的极大边双连通子图被称为“边双连通分量”，简记为“e-DCC”。二者统称为“双连通分量”，简记为“DCC”。
树的割顶
(割顶和割点没区别,说法不同而已)
在无向连通图中，如果将其中一个点以及所有连接该点的边去掉，图就不再连通，那么这个点就叫做割点（cut vertex / articulation point）.
Tarjan算法可以用于求割点(实际上这个已经包含到下面的点双里面了)
- 首先选定一个根节点，从该根节点开始dfs整个图。
-
对于根节点,如果有2棵即以上的子树，就是割点。因为如果去掉这个点，这两棵子树就不能互相到达。
-
对于非根节点,我们维护两个数组
dfn[]和low[]，dfn[u]表示顶点u第几个被（首次）访问，low[u]表示顶点u及其子树中的点，通过非父子边（回边），能够回溯到的最早的点（dfn最小）的dfn值（但不能通过连接u与其父节点的边）。对于边(u, v)，如果low[v]>=dfn[u]，此时u就是割点。
- 怎么计算
low[u]。
-
假设当前顶点为u，则默认
low[u]=dfn[u]，即最早只能回溯到自身。 -
有一条边(u, v)，如果v未访问过，继续DFS，DFS完之后，
low[u]=min(low[u], low[v])； -
如果v访问过（且u不是v的父亲），就不需要继续DFS了，一定有
dfn[v]<dfn[u]，low[u]=min(low[u], dfn[v])。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// cut[i]为1表示i点是割点
void tarjan (int u,int fa){
DFN[u]=LOW[u]=++idx;
int child=0;
for (int i=head[u];i!=0;i=pre[i].mark){
int nx=pre[i].nxt;
if (!DFN[nx]){
tarjan (nx,fa);
LOW[u]=min (LOW[u],LOW[nx]);
if (LOW[nx]>=DFN[u]&&u!=fa)
cut[u]=1;
if(u==fa)
child++;
}
LOW[u]=min (LOW[u],DFN[nx]);
}
if (child>=2&&u==fa)
cut[u]=1;
}
点双连通分量
本质上是基于上述求割点的算法,将割点的子树看作是强连通分量
处理方法如下
-
我们将点按照访问顺序入栈
-
当我们确定 x 是割点，即 x 的某个子节点 y 满足
low[y] ≥ dfn[x]时，我们将栈中的点依次弹出，直到栈顶为 x，x 和我们弹出的这些点构成了一个点双连通分量。注意：x 不能弹出，因为 x 可能属于多个点双连通分量。 -
如果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
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
71
72
// 各个版本有些差异,pre数组其实是dfs访问到节点的时间戳
// 执行之后,bcc里面每个元素都是一个点双连通分量(注:一个点可能存在于多个点双连通分量中)
// 注意,可能会出现一些只有两个点的双连通分量,在统计环的时候要注意
stack<Edge> S;
int n,m,k;
int pre[maxn],dfs_clock,iscut[maxn],low[maxn],bcc_cnt,bccno[maxn];
vector<int> bcc[maxn];
int tarjan(int u,int fa) {
int lowu=pre[u]=++dfs_clock;
int child=0;
for(int i=head[u]; i+1; i=edge[i].next) {
int v=edge[i].v;
Edge e=(Edge) {
u,v,0,0
};
if(!pre[v]) {
S.push(e);
child++;
int lowv=tarjan(v,u);
lowu=min(lowv,lowu);
if(lowv>=pre[u]) {
iscut[u]=true; // u是割点
bcc_cnt++;
bcc[bcc_cnt].clear();
for(;;) { // 弹栈
Edge x = S.top();
S.pop();
if(bccno[x.u]!=bcc_cnt) {
bcc[bcc_cnt].push_back(x.u);
bccno[x.u]=bcc_cnt;
}
if(bccno[x.v]!=bcc_cnt) {
bcc[bcc_cnt].push_back(x.v);
bccno[x.v]=bcc_cnt;
}
if(x.u==u&&x.v==v)
break;
}
}
} else if(pre[v]<pre[u]&&v!=fa) {
S.push(e);
lowu=min(lowu,pre[v]);
}
}
if(fa<0&&child==1) { // 如果u是根节点,而且只有一个儿子,那么就不是割点
iscut[u]=0;
}
return lowu;
}
void tarjan_init(){ // 也包括链式前向星的初始化
for(int i=0; i<=n; ++i) {
head[i]=-1;
pre[i]=0;
bcc[i].clear();
iscut[i]=0;
bccno[i]=0;
}
while(!S.empty()) {
S.pop();
}
//S.clear();
cnt=0;
}
void work(){
dfs_clock=bcc_cnt=0;
for(int i=1; i<=n; ++i) {
if(!pre[i])
tarjan(i,-1);
}
}
树的割边
割边也就是桥
思路与割点一样，如果一个点 x 不可以不通过 边 L 到达点 y ，则边 L 是一条割边
求割边的代码已经集成到了下面的模板
边连通分量
对于边_双连通分量的求解简单多了，我们先找出所有的桥，并将其做上标记。然后在利用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
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
int dfs_findbridge(int u,int fa) //找出所有的桥
{
int lowu = pre[u] = ++dfs_clock;
for(int i=head[u];i!=-1;i=edges[i].next)
{
int v = edges[i].v;
if(!pre[v])
{
int lowv = dfs_findbridge(v,u);
lowu = min(lowu,lowv);
if(lowv > pre[u]) // 注:这里没有等号,切记切记(点双才有等号)
{
isbridge[edges[i].no] = 1; //桥
}
}
else if(pre[v] < pre[u] && v != fa)
{
lowu = min(lowu,pre[v]);
}
}
return lowu;
}
void dfs_coutbridge(int u,int fa) //保存边_双连通分量的信息
{
ebc[ebcnum].push_back(u);
pre[u] = ++dfs_clock;
for(int i=head[u];i!=-1;i=edges[i].next)
{
int v = edges[i].v;
if(!isbridge[edges[i].no] && !pre[v]) dfs_coutbridge(v,u);
}
}
void init()
{
memset(pre,0,sizeof(pre));
memset(isbridge,0,sizeof(isbridge));
memset(head,-1,sizeof(head));
e = 0; ebcnum = 0;
}
void work(){
init();
dfs_findbridge(1,-1);
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++)
{
if(!pre[i])
{
ebc[ebcnum].clear();
dfs_coutbridge(i,-1);
ebcnum++;
}
}
for(int i=0;i<ebcnum;i++)
{
for(int j=0;j<ebc[i].size();j++)
cout<<ebc[i][j]<<" ";
cout<<endl;
}
}
