数据结构-地下迷宫探索

题目
地下迷宫探索

我们在回顾前辈们艰苦卓绝的战争生活的同时,真心钦佩他们的聪明才智。在现在和平发展的年代,对多数人来说,探索地下通道或许只是一种娱乐或者益智的游戏。本实验案例以探索地下通道迷宫作为内容。

假设有一个地下通道迷宫,它的通道都是直的,而通道所有交叉点(包括通道的端点)上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点?

输入格式:

输入第一行给出三个正整数,分别表示地下迷宫的节点数$N$(1<$N$≤1000,表示通道所有交叉点和端点)、边数$M$(≤3000,表示通道数)和探索起始节点编号$S$(节点从1到$N$编号)。随后的$M$行对应$M$条边(通道),每行给出一对正整数,分别是该条边直接连通的两个节点的编号。

输出格式:

若可以点亮所有节点的灯,则输出从$S$开始并以$S$结束的包含所有节点的序列,序列中相邻的节点一定有边(通道);否则虽然不能点亮所有节点的灯,但还是输出点亮部分灯的节点序列,最后输出0,此时表示迷宫不是连通图。

由于深度优先遍历的节点序列是不唯一的,为了使得输出具有唯一的结果,我们约定以节点小编号优先的次序访问(点灯)。在点亮所有可以点亮的灯后,以原路返回的方式回到起点。

输入样例1:

6 8 1
1 2
2 3
3 4
4 5
5 6
6 4
3 6
1 5

输出样例1:

1 2 3 4 5 6 5 4 3 2 1

输入样例2:

6 6 6
1 2
1 3
2 3
5 4
6 5
6 4

输出样例1:

6 4 5 4 6 0

解题方法:

这里主要是要有DFS的回溯,当程序从dfs(v)中跳出来时,输出它刚刚的u,就相当于时退一步的回溯。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <vector>
#include <algorithm>
#define UNVISITED 0
#define VISITED 1
using namespace std;
typedef vector<int> vi;
vi dfs_num;
vector<vi> AdjList;
int cnt = 1, space = 0;
void (int u){
dfs_num[u] = VISITED;
if(!space){ printf("%d", u); space++; }
else printf(" %d", u);
for(int j = 0;j < (int)AdjList[u].size();j++){
int v = AdjList[u][j];
if(dfs_num[v]==UNVISITED){
cnt++;
dfs(v);
printf(" %d", u);
}
}
}
int main(){
int N, M, S, x, y;
scanf("%d %d %d", &N, &M, &S);
AdjList.assign(N+1, vi()); dfs_num.assign(N+1, UNVISITED);
for(int i = 0;i < M;i++){
scanf("%d %d", &x, &y);
AdjList[x].push_back(y);
AdjList[y].push_back(x);
}
for(int i = 1;i <= N;i++){
sort(AdjList[i].begin(), AdjList[i].end());
}
dfs(S);
if(cnt < N) printf(" 0");
return 0;
}