5-11 列出连通集 (25分) 给定一个有NN个顶点和EE条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N-1N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入样例: 8 6 0 7 0 1 2 0 4 1 2 4 3 5 输出样例:
{ 0 1 4 2 7 } { 3 5 } { 6 } { 0 1 2 7 4 } { 3 5 } { 6 }
#include <stdio.h>#include <queue>using namespace std;int n,e;int s[12][12]={0};int q[12]={0};int p[12]={0};void dfs(int k){//深度优先遍历 PRintf("%d ",k); q[k]=1; int i,j; for(i=0;i<n;i++){ if(s[k][i]==1&&q[i]!=1){ dfs(i); } }}void bfs(int k){ //广度优先遍历 p[k]=1; //标记数组 int u; queue<int>w; w.push(k); while(!w.empty()){ u=w.front(); w.pop(); printf("%d ",u); for(int i=0;i<n;i++){ if(s[u][i]==1&&p[i]!=1){ w.push(i); p[i]=1; } } }}int main(){ scanf("%d%d",&n,&e); int k,m; for(int i=0;i<e;i++){ scanf("%d%d",&k,&m); s[k][m]=1; s[m][k]=1; } for(int i=0;i<n;i++){ if(q[i]==0){ printf("{ "); dfs(i); printf("}/n"); } } for(int i=0;i<n;i++){ if(p[i]==0){ printf("{ "); bfs(i); printf("}/n"); } } return 0;}新闻热点
疑难解答
