7-6 列出连通集
输入样例:
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 }注: bfs中 queue的 进 出 顺序一样，可以在进队列时输出，也可在出队列时。
代码：
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int mp[10][10],vst[10];
int n,m;
queue<int>q;
void dfs(int u){
printf("%d ",u);
vst[u]=1;
for(int i=0;i<n;i++){
if(mp[u][i]&&!vst[i]) dfs(i);
}
}
void bfs(){
while(q.size()){
int u=q.front();q.pop();
printf("%d ",u);
for(int i=0;i<n;i++){
if(mp[u][i]&&!vst[i]) q.push(i),vst[i]=1;
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y; scanf("%d%d",&x,&y);
mp[x][y]=mp[y][x]=1;
}
for(int i=0;i<n;i++){
if(vst[i]) continue;
printf("{ ");
dfs(i);
printf("}\n");
}
memset(vst,0,sizeof(vst));
for(int i=0;i<n;i++){
if(vst[i]) continue;
printf("{ ");
q.push(i);vst[i]=1;
bfs();
printf("}\n");
}
return 0;
}