[C++知识库]7-33 地下迷宫探索 (30 分)c语言

原题：https://pintia.cn/problem-sets/15/problems/860

看题目给出的输入输出样例就知道，这是要我们对该图从起点S出发进行深度优先搜索（DFS）遍历该图，同时要我们给出返回的路线，那么只要对DFS稍加修改就可以实现了。题中还要求说要我们判断是否能够全部走完，如果不能还要在结尾输出0

#include<stdio.h>
#define MAXSIZE 1010
int G[MAXSIZE][MAXSIZE];
int n,m,k; 
int visit[MAXSIZE];
int FLAG=0; //控制输出空格 
int cnt=0;//记录下往回走了几步，若是n-1步那么就已经往回走个遍，否则说明没有全部走遍 
void dfs(int s)//只要S节点进入了DFS就输出该点
{
	int i;
	if(!FLAG)//结尾处不能有空格我们在这里处理一下
	{
	printf("%d",s);	
	FLAG++;
	}
	else if(FLAG)
	{
		printf(" %d",s);
		
	}
	visit[s]=1;
	for(i=1;i<=n;i++)
	{
		if(G[s][i]&&!visit[i])
		{
			visit[i]=1;
			dfs(i);			
			printf(" %d",s);//加多一句输出语句，只要所有点访问完了就会返回到这里往回走了
			cnt++;//对返回的点进行计数，如果返回的次数不是n-1那么说明并没有全部走完
		}
	}
}

int main()
{
	int i;
	scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		G[x][y]=G[y][x]=1;
	}
	dfs(k);
	if(cnt!=n-1)
	printf(" 0");
	return 0;
}