33OJ
登录 注册

#H0004. 遍历图

遍历图

题目描述

小明最近正在学习图的遍历,和上次一样,他想请你帮他写一个程序,判断自己的输出对不对,输入由小明给出。 他想用深度优先搜索和广度优先搜索来解题,所以这两种正确输出都必须由你给出。

按边的点从小到大的顺序遍历,题目不保证联通(用多个连通块),每个连通块从连通块内最小的点开始遍历。

输入格式

输入第一行有两个数n,m表示有几个点,几个边。 下面的m行,每行两个数u,v表示边(u,v)。

输出格式

共两行,第一行是广度优先搜索的结果。 第二行是深度优先搜索。

8 8
1 3
1 2
2 5
2 4
3 7
3 6
4 8
5 8

1 2 3 4 5 6 7 8
1 2 4 8 5 3 6 7

数据规模与约定

0<=n,m<=1000,1<=u,v<=n。

此乃无向图。