2021秋季《数据结构》_EOJ 1087.地下迷宫探索

题目

思路

• 相较于一般dfs，还需要输出返回路径。利用函数调用栈的特性，在每次调用dfs的位置下方加入输出当前点的命令
• 不存在路径的两点之间初始值赋为正无穷
• 记得判断连通的题目要求

代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1001int path[MAXN][MAXN] = {
     {
    0} };
int book[MAXN] = {
     0 };
int n, m, s;void dfs(int u)  // u为当前顶点
{
    book[u] = 1;  // 走过了ucout << u << ' ';for (int i = 1; i <= n; i++){
    if (path[u][i] && !book[i])// u,i之间有路且i没被走过{
    dfs(i);cout << u << ' ';}}
}// dfs
int main()
{
    cin >> n >> m >> s;for (int i = 0; i < m; i++){
    int x, y; cin >> x >> y;// 无向图path[x][y] = 1;path[y][x] = 1;}dfs(s);int flag = 1;for (int i = 1; i <= n; i++){
    if (!book[i])  // 还有没被走过的顶点{
    flag = 0;break;}}if (!flag) cout << 0;cout << endl;return 0;
}