给定一个无向图,从指定的起点顶点开始进行深度优先搜索(DFS)遍历,按照访问顺序输出所有顶点的编号。
顶点1(起点)首先被访问
从顶点1出发,访问邻居顶点2
从顶点2出发,访问邻居顶点3(顶点1已访问过,跳过)
从顶点3出发,访问邻居顶点4(顶点2已访问过,跳过)
所有顶点访问完毕,遍历顺序为:1 → 2 → 3 → 4
输入样例
4 5 1
1 2
1 3
2 3
2 4
3 4
输出样例
1 2 3 4
样例解释
第一行包含三个整数 n, m, s,分别表示图的顶点数、边数和遍历的起点顶点。
接下来 m 行,每行包含两个整数 u, v,表示顶点 u 和顶点 v 之间有一条无向边。
输出一行,包含若干个用空格分隔的整数,表示从起点 s 开始进行 DFS 遍历访问到的顶点顺序。
1 ≤ n ≤ 1000
0 ≤ m ≤ n × (n - 1) / 2
1 ≤ s ≤ n
1 ≤ u, v ≤ n
保证图是简单无向图(无自环,无重边)