题目：输出无向连通图各个连通分量。
输入描述。输入文件中包含多个测试数据，每个测试数据的格式为：第1行为两个整数n和m，分别表示顶点个数和边数，然后有m行，每行表示一条边，为这条边的两个顶点的序号，顶点序号从1开始计起。假定无向图是连通的（可能存在割点，也可能没有割点）。n = m = 0时表示输入结束。
输出描述。对每个测试数据，以“u v”的形式依次输出各连通分量中的每条边，每个连通分量的数据占一行，用空格分隔每条边。各测试数据的输出之间用空行分隔开。
#include <iostream> #include <cstring> using namespace std; const int MAXN = 25; const int MAXM = 50; int MIN(int a, int b) { return a > b ? b : a; } struct edge { int u, v; void output() { cout<<u<<"-"<<v; } bool Compare( edge &t ) { return (u == t.u && v == t.v) || (u == t.v && v == t.u); } }; edge edges[MAXM];//Êý×éÄ£Äâ±ßÕ» int top; int Edge[MAXN][MAXN]; int visited[MAXN]; int n, m; int tmpdfn; int dfn[MAXN]; int low[MAXN]; void DFS( int u ) { for(int v = 1; v <= n; v++) { if(Edge[u][v] == 1) { edge t; t.u = u, t.v = v; edges[++top] = t; Edge[u][v] = Edge[v][u] = 2; if(!visited[v]) { visited[v] = 1; dfn[v] = low[v] = ++tmpdfn; DFS( v ); low[u] = MIN(low[u], low[v]); if(low[v] >= dfn[u]) { bool firstedge = true; while(1) { if(top < 0) break; if(firstedge) firstedge = false; else cout<<" "; edge t1; t1 = edges[top]; t1.output(); edges[top].u = 0, edges[top--].v = 0; if(t1.Compare(t)) break; } cout<<endl; } } else low[u] = MIN(low[u], dfn[v]); } } } int main() { int i, u, v; int kcase = 1; while(1) { cin>>n>>m; if(m == 0 && n == 0) break; memset(Edge, 0, sizeof(Edge)); for(i = 1; i <= m; ++i) { cin>>u>>v; Edge[u][v] = Edge[v][u] = 1; } if(kcase++ > 1) cout<<endl; low[1] = dfn[1] = 1; tmpdfn = 1; memset(visited, 0, sizeof(visited)); visited[1] = 1; memset(edges, 0, sizeof(edges)); top = -1; DFS( 1 ); } return 0; }
输入输出样例：
输入：
7 9
1 2
1 3
1 6
1 7
2 3
2 4
2 5
4 5
6 7
4 4
1 2
2 3
3 4
4 1
0 0
输出：
5-2 4-5 2-4
3-1 2-3 1-2
7-1 6-7 1-6
4-1 3-4 2-3 1-2
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/233311.html原文链接：https://javaforall.net
