双连通分量模板以及对一些不好理解点的解释

双连通分量(biconnected component, 简称bcc)概念&＃xff1a;

双连通分量有点双连通分量和边双连通分量两种。若一个无向图中的去掉任意一个节点&＃xff08;一条边&＃xff09;都不会改变此图的连通性&＃xff0c;即不存在割点&＃xff08;桥&＃xff09;&＃xff0c;则称作点&＃xff08;边&＃xff09;双连通图。一个无向图中的每一个极大点&＃xff08;边&＃xff09;双连通子图称作此无向图的点&＃xff08;边&＃xff09;双连通分量。求双连通分量可用Tarjan算法。--百度百科

先学一下tarjan算法以及求割点割边的算法之后&＃xff0c;再看会比较好理解一些。(1.Tarjan 2.图的割点割边)

先看比较难写点双连通分量的求法&＃xff0c;直接看代码理解。另附图一张&＃xff1a;

Code&＃xff1a;

#include
using namespace std;
const int maxn &＃61; 110;
const int maxm &＃61; 10010;
struct node
{
int u, v, next;
}edge[maxm], tp;
int n, m; //点数&＃xff0c;边数
int head[maxn], no;
int add_bcc[maxn];//去掉该点之后能增加的bcc数目
int index; //时间戳
int yltd; //图的初始连通分量
int num[maxn], low[maxn];//时间戳和能回到的最早时间戳
int iscut[maxn];//是否为割点
int bccno[maxn], bcc_cnt; //bccno[i]表示i属于哪个bcc
stack S; //存储bcc边
vector bcc[maxn];
inline void init()
{
no &＃61; 0;
memset(head, -1, sizeof head);
}
inline void add(int u, int v)
{
edge[no].u &＃61; u; edge[no].v &＃61; v;
edge[no].next &＃61; head[u]; head[u] &＃61; no&＃43;&＃43;;
edge[no].u &＃61; v; edge[no].v &＃61; u;
edge[no].next &＃61; head[v]; head[v] &＃61; no&＃43;&＃43;;
}
inline void input()
{
int u, v;
for(int i &＃61; 1; i <&＃61; m; &＃43;&＃43;i)
{
scanf("%d %d", &u, &v);
add(u, v);
}
}
void tarjan(int cur, int father)
{
int child &＃61; 0;
num[cur] &＃61; low[cur] &＃61; &＃43;&＃43;index;
int k &＃61; head[cur];
while(k !&＃61; -1)
{
int v &＃61; edge[k].v;
if(!num[v])
{
S.push(edge[k]);
&＃43;&＃43;child;
tarjan(v, cur);
low[cur] &＃61; min(low[cur], low[v]);
if(low[v] >&＃61; num[cur])
//把更节点看做普通的节点&＃xff0c;对根节点这个条件是一定满足的&＃xff0c;
//可以实现把回溯到根节点剩下的出栈&＃xff0c;其实这就是一个新的双连通分量
{
iscut[cur] &＃61; 1;
&＃43;&＃43;add_bcc[cur];
&＃43;&＃43;bcc_cnt;//准备把新的双连通分量加入bcc
bcc[bcc_cnt].clear();
while(true)
{
tp &＃61; S.top(); S.pop();
if(bccno[tp.u] !&＃61; bcc_cnt)
{
bcc[bcc_cnt].push_back(tp.u);
bccno[tp.u] &＃61; bcc_cnt;
}
if(bccno[tp.v] !&＃61; bcc_cnt)
{
bcc[bcc_cnt].push_back(tp.v);
bccno[tp.v] &＃61; bcc_cnt;
}
if(tp.u &＃61;&＃61; edge[k].u && tp.v &＃61;&＃61; edge[k].v) break;
}
}
}
else if(num[v] {
//num[v] //访问过了。然后再从cur访问&＃xff0c;如果不判断就会将这个点加入S&＃xff0c;造成错误&＃xff0c;见上图。
//可以看到时间戳走到6再次回溯到2时&＃xff0c;还能通过2对2-4这条边进行一次尝试&＃xff0c;不判断的话4会被加到S
S.push(edge[k]);
low[cur] &＃61; min(low[cur], num[v]);
}
k &＃61; edge[k].next;
}
if(father <0)
{
//把根节点看做普通节点了&＃xff0c;所以下面最后的特殊判断必需。
if(child > 1) iscut[cur] &＃61; 1, add_bcc[cur] &＃61; child-1;
else iscut[cur] &＃61; 0, add_bcc[cur] &＃61; 0;
}
}
void Find_Cut(int l, int r)
{
index &＃61; bcc_cnt &＃61; yltd &＃61; 0;
memset(add_bcc, 0, sizeof add_bcc);
memset(num, 0, sizeof num);
memset(iscut, 0, sizeof iscut);
memset(bccno, 0, sizeof bccno);
memset(low, 0, sizeof low);
for(int i &＃61; l; i <&＃61; r; &＃43;&＃43;i)
{
if(!num[i]) tarjan(i, -1), &＃43;&＃43;yltd;
}
}
void PutAll(int l, int r)
{
for(int i &＃61; l; i <&＃61; r; &＃43;&＃43;i)
{
if(iscut[i]) printf("%d是割点&＃xff0c;", i);
printf("去掉点%d之后有%d个双连通分量\n", i, add_bcc[i]&＃43;yltd);
}
}
void PutBcc()
{
printf("有%d个BCC\n", bcc_cnt);
for(int i &＃61; 1; i <&＃61; bcc_cnt; &＃43;&＃43;i)
{
printf("BCC%d有%d个点: ", i, bcc[i].size());
for(int j &＃61; 0; j printf("\n");
}
}
int main()
{
while(~scanf("%d %d", &n, &m))
{
init();
input();
Find_Cut(1, n);
PutAll(1, n);
PutBcc();
}
return 0;
}
/*
测试样例&＃xff1a;
8 11
1 2
2 3
3 4
2 4
2 5
2 6
5 6
1 7
1 8
7 8
2 8
*/

上面仔细模拟模拟就能想通(例题&＃xff1a;
UVALive 5135
)。

双连通分量的求法就比较朴素了。

Code&＃xff1a;

#include
using namespace std;
const int maxn &＃61; 110;
const int maxm &＃61; 10010;
struct node
{
int u, v, next;
}edge[maxm];
int n, m; //点数&＃xff0c;边数
int head[maxn], no;
int index; //时间戳
int num[maxn], low[maxn];//时间戳和能回到的最早时间戳
int iscutedge[maxm];//是否为割边&＃xff0c;存邻接表的索引
inline void init()
{
no &＃61; 0;
memset(head, -1, sizeof head);
}
inline void add(int u, int v)
{
edge[no].u &＃61; u; edge[no].v &＃61; v;
edge[no].next &＃61; head[u]; head[u] &＃61; no&＃43;&＃43;;
edge[no].u &＃61; v; edge[no].v &＃61; u;
edge[no].next &＃61; head[v]; head[v] &＃61; no&＃43;&＃43;;
}
inline void input()
{
int u, v;
for(int i &＃61; 1; i <&＃61; m; &＃43;&＃43;i)
{
scanf("%d %d", &u, &v);
add(u, v);
}
}
void tarjan(int cur, int father)
{
num[cur] &＃61; low[cur] &＃61; &＃43;&＃43;index;
int k &＃61; head[cur];
while(k !&＃61; -1)
{
int v &＃61; edge[k].v;
if(!num[v])
{
tarjan(v, cur);
low[cur] &＃61; min(low[cur], low[v]);
if(low[v] > num[cur])
{
//把割边的两个方向的边都标记
iscutedge[k] &＃61; iscutedge[k^1] &＃61; 1;
}
}
else if(edge[k].v !&＃61; father)
{
low[cur] &＃61; min(low[cur], num[v]);
}
k &＃61; edge[k].next;
}
}
//找出割边标记上
void Find_CutEdge(int l, int r)
{
index &＃61; 0;
memset(iscutedge, 0, sizeof iscutedge);
memset(num, 0, sizeof num);
memset(low, 0, sizeof low);
for(int i &＃61; l; i <&＃61; r; &＃43;&＃43;i)
{
if(!num[i]) tarjan(i, -1);
}
}
int dfs(int cur)
{
num[cur] &＃61; 1;
int flag &＃61; 0; //判断是否存在边双联通分量&＃xff0c;以免多输出换行
for(int k &＃61; head[cur]; k !&＃61; -1; k &＃61; edge[k].next)
{
if(iscutedge[k]) continue;
flag &＃61; 1;
iscutedge[k] &＃61; iscutedge[k^1] &＃61; 1;
printf("(%d, %d) ", cur, edge[k].v);
if(!num[edge[k].v]) dfs(edge[k].v);
}
return flag;
}
//dfs输出就能得到相应的双连通分量
void PutBccEdge(int l, int r)
{
memset(num, 0, sizeof num);
printf("双连通分量的边有&＃xff1a;\n");
for(int i &＃61; l; i <&＃61; r; i&＃43;&＃43;)
if(!num[i])
{
if(dfs(i)) cout < }
}
int main()
{
while(~scanf("%d %d", &n, &m))
{
init();
input();
Find_CutEdge(1, n);
PutBccEdge(1, n);
}
return 0;
}
/*
测试样例&＃xff1a;
8 10
1 2
2 3
3 4
2 4
2 5
2 6
5 6
1 7
1 8
7 8
*/

找完割边然后进行DFS输出所有边双连通分量所包含的边~(例题&＃xff1a;poj 3352)。

Code2(正确模板方法):

#include
using namespace std;
const int maxn &＃61; 25005;
const int maxm &＃61; 1e5&＃43;5;
struct node {
int u, v, next;
} edge[maxm];
int no, head[maxn];
int idx, dfn[maxn], low[maxn];
int top, S[maxn];
int bcc_cnt, cut;
int bccno[maxn];
vector bcc[maxn];
int n, m;
void init()
{
no &＃61; 0;
memset(head, -1, sizeof head);
}
void add(int u, int v)
{
edge[no].u &＃61; u; edge[no].v &＃61; v;
edge[no].next &＃61; head[u]; head[u] &＃61; no&＃43;&＃43;;
}
void tarjan(int u, int fa)
{
dfn[u] &＃61; low[u] &＃61; &＃43;&＃43;idx;
S[&＃43;&＃43;top] &＃61; u;
for(int k &＃61; head[u]; k&＃43;1; k &＃61; edge[k].next)
{
int v &＃61; edge[k].v;
if(!dfn[v])
{
tarjan(v, u);
low[u] &＃61; min(low[u], low[v]);
if(low[v] > dfn[u])
{
&＃43;&＃43;cut; //割边&＃43;1
}
}
else if(v !&＃61; fa)
{
low[u] &＃61; min(low[u], dfn[v]);
}
}
if(dfn[u] &＃61;&＃61; low[u])
{
&＃43;&＃43;bcc_cnt; //边双连通分量&＃43;1
do
{
bcc[bcc_cnt].push_back(S[top]);
bccno[S[top]] &＃61; bcc_cnt;
--top;
}
while(S[top&＃43;1] !&＃61; u);
}
}
void work()
{
memset(dfn, 0, sizeof dfn);
memset(bccno, 0, sizeof bccno);
idx &＃61; top &＃61; bcc_cnt &＃61; cut &＃61; 0;
for(int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i)
if(!dfn[i]) tarjan(i, i);
for(int i &＃61; 1; i <&＃61; bcc_cnt; &＃43;&＃43;i)
{
cout < for(int j &＃61; 0; j cout < cout < }
}
int main()
{
init();
cin >> n >> m;
for(int i &＃61; 1; i <&＃61; m; &＃43;&＃43;i)
{
int u, v;
cin >> u >> v;
add(u, v); add(v, u);
}
work();
return 0;
}
/*
input&＃xff1a;
6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6
output&＃xff1a;
1: 5 6 4
2: 2 3 1
*/