题目描述(ID:12370)
标题: dfs序
标签: 搜索 图的遍历
详情: 请输出一个图的使用深度优先搜索的顺序(先访问编号小的节点再访问编号大的节点)和每个顶点的间戳编号即这个顶点是第几个被访问到的
输入格式:
第一行的有两个整数n m ,n个顶点,m条边
接下来m行每行是一条类似“a b”这样的数据表示a号顶点和b号顶点之间可以相互到达
输出格式:
输出有两行
第一行是依次输出深度优先搜索的顺序每个顶点的编号用空格隔开
第二行输出每个顶点的时间戳编号即这个顶点是第几个被访问到的
限制: 1<=n<=1000
1<=m<=300000
样例:

输入

7 9
1 3
1 5
3 4
3 2
3 5
5 6
5 7
6 7
2 4

输出

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

输入

13 18
1 5
1 4
3 2
5 2
6 2
2 12
6 7
3 7
3 8
7 8
10 6
6 11
10 11
12 13
12 9
13 9
4 2
5 6

输出

1 4 2 3 7 6 5 10 11 8 12 9 13
1 3 4 2 7 6 5 10 12 8 9 11 13
登录并解答