思路与算法

给定一棵无根树（节点编号 1 到 n），可以从任意节点出发做 DFS，且每个节点遍历相邻节点的顺序可以任意安排。希望得到整段访问序列在字典序上最小的结果。

关键观察

字典序最小的 DFS 序列意义是：尽早访问小编号的节点。

• 起点可以任意选，显然选编号最小的节点作为起点最有利（因为序列第一个元素越小越好）。编号范围是 1..n，起点选 1 即可。
• 在 DFS 过程中，每个节点应先访问编号小的未访问邻居，才能保证当前局部扩展在字典序上最小。

题目内容

给定一棵无根树，包含 $n$ 个节点，节点编号为 $1$ ~ $n$ 。小 $C$ 可以从任意节点出发，对这棵树进行深度优先搜索($DFS$)遍历，记录访问节点的编号序列作为 $DFS$ 序。

在遍历过程中，每个节点可以按照任意顺序访问其相邻节点。小$C$希望得到字典序最小的 $DFS$ 序。请你计算并输出该序列。

【名词解释】

• $DFS$ 遍历：DFS遍历 指从指定起始节点出发，每次访问一个未被访问的相邻节点，并继续递归，直到所有可达节点均被访问。