图的遍历(Graph Traversal)

题目描述

我们已经学会用邻接矩阵存储一张无向图。现在要从某个起点出发，对图进行一次深度优先搜索（DFS）：

1. 从 1 号顶点出发，访问并记录当前顶点；
2. 从当前顶点出发，寻找一个与它有边相连且尚未访问的顶点，走过去继续搜索；
3. 如果当前顶点所有相连的顶点都已经访问过，就回溯到上一个顶点；
4. 重复以上过程，直到所有顶点都被访问。

为了让答案唯一，规定：每次寻找下一个顶点时，按顶点编号从小到大依次尝试。

这样依次记录下被访问顶点的编号，就得到了图的 DFS 遍历序列（DFS 序）。请你输出这个序列。

输入格式

第一行两个整数 n 和 m，分别表示顶点个数和边的条数。

接下来 m 行，每行两个整数 u 和 v，表示顶点 u 和顶点 v 之间有一条无向边。

输出格式

输出一行，包含 n 个整数，表示从 1 号顶点出发进行深度优先搜索所得到的顶点访问顺序，相邻两个数之间用一个空格隔开。

样例输入

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

样例输出

1 2 3 5 4

样例解释

• 从 1 出发，与它相连且未访问的顶点有 2、3，先访问编号小的 2；
• 在 2 处，相连且未访问的有 3、4、5，先访问 3；
• 在 3 处，相连且未访问的有 5，访问 5；
• 在 5 处，相连且未访问的有 4，访问 4；
• 所有顶点访问完毕，得到序列 1 2 3 5 4。

数据范围

• 1 ≤ n ≤ 1000
• 0 ≤ m ≤ n(n-1)/2
• 1 ≤ u, v ≤ n，u ≠ v
• 保证图是连通的（即从 1 号顶点出发可以到达所有顶点），没有重边和自环

提示

用邻接矩阵存图，配合一个访问标记数组，DFS 的框架如下：

dfs(顶点 u):
    标记 u 已访问，并输出 u
    for v 从 1 到 n:        // 从小到大枚举，保证答案唯一
        如果 u 和 v 有边 且 v 未访问:
            dfs(v)

注意：图中的边是无向的，存图时要记得 a[u][v] = a[v][u] = 1。