问题描述

• 现有一无向图（可能不连通），输出该图形的深度遍历和广度遍历结果。

输入格式

• 输入文件第一行为 n 和 m，表示有 n 个顶点（1 <= n <= 10,000），编号从 1 到 n，m 表示有该图有 m 条边（1 <= m <= 100,000），接下来 m 行，每行两个整数 i 和 j，表示顶点 i 到顶点 j 有一条边。

输出格式

• 输出为两行，第一行为深度遍历的结果，第二行为广度遍历的结果，每个顶点间用一个‘-’符号隔开，假定每次都从编号最小的点开始遍历，且扫描边的时候优先遍历编号低的顶点。

样例

stdin:

4 2
1 2
2 4

stdout:

1-2-4-3
1-2-4-3

我的代码

#include<bits/stdc++.h>
using namespace std;
long long a[1001][1001],visd[100000],visb[100000];
long long n,m;
long long dfs(long long bt){
	if(bt==1){
		cout<<bt;
		visd[bt]=1;
	}else {
		cout<<"-"<<bt;
		visd[bt]=1;
	}
	for(int j=bt;j<=n;j++)
		if(a[bt][j]==1)dfs(j);
	return 0;
}
long long bfs(long long bt){
	if(bt==1){
		cout<<bt;
		visb[bt]=1;
	}
	for(int i=bt;i<=n;i++){
		if(a[bt][i]==1){
			cout<<"-"<<i;
			visb[i]=1;
		}
	}
	for(int i=bt;i<=n;i++){
		if(a[bt][i]==1)bfs(i);
	}
	return 0;
}
int main(){

	
	cin>>n>>m;
	long long x,y;
	for(int i=0;i<m;i++){
		cin>>x>>y;
		a[x][y]=a[y][x]=1;
	}
	dfs(1);
	for(int i=1;i<=n;i++){
		if(visd[i]==0){
			if(i==1){
				cout<<i;
			}else{
				cout<<"-"<<i;
			}
		}
	}
	cout<<endl;
	bfs(1);
	for(int i=1;i<=n;i++){
		if(visb[i]==0){
			if(i==1){
				cout<<i;
			}else{
				cout<<"-"<<i;
			}
			
		}
	}
 	return 0;
}