[数据结构与算法]广度优先遍历

题目描述

输入格式

输出格式

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

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

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int g[101][101],visit[101];
int m,n;
queue<int> q;
void bfs(int x){
?? ?visit[x]=1;
?? ?q.push(x);
?? ?while(!q.empty()){
?? ??? ?int cur=q.front();
?? ??? ?for(int i=1;i<=m;i++){
?? ??? ??? ?if(g[cur][i]==1&&visit[i]==0){
?? ??? ??? ??? ?q.push(i);
?? ??? ??? ??? ?visit[i]=1;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?cout<<q.front()<<" ";
?? ??? ?q.pop();
?? ?}
?? ?cout<<endl;
?? ?return;
}
int main(){
?? ?cin>>m>>n;
?? ?int x,y;
?? ?for(int i=1;i<=n;i++){
?? ??? ?cin>>x>>y;
?? ??? ?g[x][y]=1;
?? ??? ?g[y][x]=1;
?? ?}
?? ?for(int i=1;i<=m;i++){
?? ??? ?bfs(i);
?? ??? ?memset(visit,0,sizeof(visit));
?? ?}
?? ?return 0;
}