【下海捕鱼】求无向图的点双连通分量（模板）

Description

给出一个n个点（编号1..n），m条边的无向图，求图的点双连通分量（Biconnected Component）。

Input Data

包含多组测试数据，每组数据格式如下： 第一行输入n,m（n<=1000, m<=10000） 下面m行每行输入u,v表示u和v之间有边。 每组数据间有一个空行。 最后一行是n=m=0，表示数据结束。

Output Data

对于每组数据，输出： 第一行点双连通分量的个数。接着每行输出一个点连通分量的顶点编号。为了保证答案的唯一性，对于每个点双连通分量请按顶点递增的顺序输出。 每组数据间有一个空行。

Input Sample

6 7 1 2 1 3 5 6 2 3 3 4 4 5 4 6

2 1 1 2

4 1 1 2

5 6 1 2 2 3 1 3 3 4 5 4 3 5

5 6 1 2 1 5 1 4 4 3 3 2 2 5

0 0

Output Sample

3 1 2 3 3 4 4 5 6

1 1 2

1 1 2

2 1 2 3 3 4 5

1 1 2 3 4 5 ————————————————————分割の线————————————————————

分析

啊呀呀呀，就是题目的意思嘛。就是求双连通分量，用tarjan算法，连代码都和”割顶与桥”差不多。 详见代码：

#include <stack> #include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 1000; struct Edge { int u,v; Edge(int uu,int vv) { u = uu; v = vv; } };//定义边的结构 stack<Edge> s;//定义一个栈来储存同一个双连通分量 struct edge { int v,next; }edges[100000]; int n,m; int tot,head[maxn]; int pre[maxn]; int dfs_clock; int bcc_cnt; int belong[maxn]; vector<int> bcc[maxn]; void add(int u,int v) { edges[tot].v = v; edges[tot].next = head[u]; head[u] = tot++; } int tarjan(int u,int fa) { int lowu = pre[u] = ++dfs_clock; int child = 0; for(int i=head[u];i!=-1;i=edges[i].next) { int v = edges[i].v; Edge e = (Edge){u,v}; if(!pre[v]) { s.push(e);//把两边压入栈中 child++;//记录子结点的数量 int lowv = tarjan(v,u);//通过孩子v更新low值 lowu = min(lowu,lowv); if(lowv >= pre[u])//如果v及其子孙无法从u以外的其他地方通过，则双连通分量增加 { bcc_cnt++;//双连通分量++ bcc[bcc_cnt].clear();//数组清零 for(;;) //效果等同于while(1) { Edge x = s.top(); s.pop();//将栈中的结点逐一弹出，并将它们划分为同一双连通分量 if(belong[x.u] != bcc_cnt) {bcc[bcc_cnt].push_back(x.u); belong[x.u] = bcc_cnt;} if(belong[x.v] != bcc_cnt) {bcc[bcc_cnt].push_back(x.v); belong[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]); } } return lowu; } int cmp(vector<int> x,vector<int>y) { int k=0; while(x[k]==y[k])k++; return x[k]<y[k]; }//开启了vector二维排序的新模式 void init() { memset(pre,0,sizeof(pre)); memset(head,-1,sizeof(head)); memset(belong,0,sizeof(belong)); tot = 0; dfs_clock = 0; bcc_cnt = 0; }//神奇的初始化 int main() { int u,v; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; init(); for(int i=0;i<m;i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u);//边表的加边处理 } for(int i=1;i<=n;i++) if(!pre[i])tarjan(i,-1); cout<<bcc_cnt<<endl; for(int i=1;i<=bcc_cnt;i++) sort(bcc[i].begin(),bcc[i].end());//把每个集合的内部进行排序 sort(bcc+1,bcc+bcc_cnt+1,cmp);//把所有集合按字典序排序 for(int i=1;i<=bcc_cnt;i++)//输出次序 { printf("%d",bcc[i][0]); for(int j=1;j<bcc[i].size();j++) printf(" %d",bcc[i][j]); printf("\n"); } cout<<endl; } return 0; }

写的不好，有需要改正的地方，请在下方评论区指出。