输入描述
输入第一行为 n 和 m,表示有 n 个结点,编号从 1 到 n,m 表示有该图有 m 条边,接下来 m 行,每行两个整数 a 和 b,表示结点 a 到结点 b 有一条边。
输出描述
输出为两行,第一行为深度遍历的结果,第二行为广度遍历的结果,每个顶点间用一个‘-’符号隔开,假定每次都从结点1开始遍历,且优先遍历编号低的,每种遍历只需要一种遍历结果。
样例输入 1
4 3 1 2 1 3 2 4
样例输出 1
1-2-4-3 1-2-3-4
#include<bits/stdc++.h>
using namespace std;
int g[105][105],v1[105],v2[105];
int n,e,a,b;
int m1,m2;
queue <int> q;
void dfs(int cnt){
m1++;
cout<<cnt;
if(m1<n) cout<<'-';
for(int i=1;i<=n;i++){
if(g[cnt][i]==1&&v1[i]==0){
v1[i]=1;
dfs(i);
}
}
}
void bfs(int cnt){
q.push(cnt);
cout<<cnt;
m2++;
if(m2<n) cout<<'-';
while(!q.empty()){
for(int i=1;i<=n;i++){
if(g[q.front()][i]==1&&v2[i]==0){
v2[i]=1;
q.push(i);
cout<<i;
m2++;
if(m2<n) cout<<'-';
}
}
q.pop();
}
}
int main(){
cin>>n>>e;
for(int i=0;i<e;i++){
cin>>a>>b;
g[a][b]=1;
g[b][a]=1;
}
for(int i=1;i<=n;i++){
if(v1[i]==0){
v1[i]=1;
dfs(i);
}
}
cout<<endl;
for(int i=1;i<=n;i++){
if(v2[i]==0){
v2[i]=1;
bfs(i);
}
}
return 0;
}