资料索引双巡

普及-⏱ 1000ms💾 256MB#P3279🏷️ BFSDFS图论遍历

题目描述

资料库共 $n$ 份资料(编号 $1 \sim n$),有 $m$ 条索引关系:资料 X → Y 表示 X 的附录中列出了 Y。 管理员从资料 $1$ 开始审阅,凡审阅某份资料时必须依次转审其附录中列出的所有尚未审阅过的资料。 对每个节点的附录按编号从小到大审阅。请分别给出深度优先(DFS)与广度优先(BFS)两种巡检顺序, 从资料 $1$ 出发,不重复、不遗漏地覆盖全部可达资料。

输入格式

第一行两个整数 $n, m$。 接下来 $m$ 行每行两个整数 $X, Y$:一条索引关系 X → Y。

输出格式

共两行:第一行为 DFS 遍历序列,第二行为 BFS 遍历序列,编号以空格分隔。

数据范围

None

样例输入 #1
8 9
1 2
1 3
1 4
2 5
2 6
3 6
4 7
5 8
6 8
样例输出 #1
1 2 5 8 6 3 4 7
1 2 3 4 5 6 7 8
样例输入 #2
1 0
样例输出 #2
1
1