#1013. 树的遍历
树的遍历
问题描述
给出一棵含有 N 个结点的树,结点编号为 1 ~ N,其中1 号为根结点。从根结点开始遍历,输出它的 DFS 和 BFS 序列。如果有多种可能的序列,输出字典序最小的。
输入
第一行:N
接下来 N-1 行,每行两个数 u, v, 表示 u 和 v 之间有一条边。
输出
两行,依次为 DFS 和 BFS 遍历的序列,具体格式见样例。注意:输出中的每个整数前面均有一个空格。
样例输入
12
1 4
1 2
3 1
2 5
6 2
11 5
5 10
4 7
4 9
8 4
12 7
样例输出
DFS: 1 2 5 10 11 6 3 4 7 12 8 9
BFS: 1 2 3 4 5 6 7 8 9 10 11 12
数据范围
1 ≤ N ≤ 50,000