7-3 地下迷宫探索 (30 分)

7-3 地下迷宫探索 (30 分)地道战是在抗日战争时期在华北平原上抗日军民利用地道打击日本侵略者的作战方式。地道网是房连房、街连街、村连村的地下工事如下图所示。我们在回顾前辈们艰苦卓绝的战争生活的同时真心钦佩他们的聪明才智。在现在和平发展的年代对多数人来说探索地下通道或许只是一种娱乐或者益智的游戏。本实验案例以探索地下通道迷宫作为内容。假设有一个地下通道迷宫它的通道都是直的而通道所有交叉点包括通道的端点上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点输入格式:输入第一行给出三个正整数分别表示地下迷宫的节点数N1N≤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输出样例2:6 4 5 4 6 0测试点#include iostream #include bits/stdc.h using namespace std; const int N3110; int vis[N]; int dis[N][N]; int m,n,d; int b[N]; int top; void dfs(int v) { b[top]v; vis[v]1; for(int i1; in; i) { if(vis[i]0dis[v][i]1) { vis[i]1; dfs(i); b[top]v; } } } int main() { scanf(%d %d %d,n,m,d); int x,y; memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); for(int i0; im; i) { scanf(%d %d,x,y); dis[y][x]dis[x][y]1; } top0; dfs(d); for(int i0; itop; i) { if(i0) { printf(%d,b[i]); } else { printf( %d,b[i]); } } if(top!2*n-1) { printf( 0); } printf(\n); return 0; }