dfs题解 | 旺仔哥哥走迷宫

突然发现没有dfs的题解，于是我来写一份（）

思路很简单，构建邻接表，然后用for循环遍历，如果找到了就输出并结束，如果找到的是t[i]==1的点，那就continue（代码里体现的是t[i]==0的时候才执行）

代码里还有注释，再结合上注释，这题真不难的

#include <bits/stdc++.h>
using namespace std;

#define sc second
#define fr first
#define int long long
#define itn long long
#define fro for
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define endl '\n'
#define all(qwq) qwq.begin(), qwq.end()
#define ui unordered_map<int, int>
#define pq priority_queue
#define pi acos(-1)

// const int dx[4] = {-1, 1, 0, 0};
// const int dy[4] = {0, 0, -1, 1};
// const int dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
// const int dy[8] = {1, 1, 1, 0, -1, -1, -1, 0};
// const int dx[12] = {-1, 0, 1, 1, 1, 0, -1, -1, 0, 2, -2, 0};
// const int dy[12] = {1, 1, 1, 0, -1, -1, -1, 0, 2, 0, 0, -2};
// const int mod = 998244353;
// const int mod = 1e9 + 7;

int m, n, k, x, y, num, op, sum = 0, cnt = 0;
string s;
vi t;
vvi e;
vi vis;
void dfs(int k)
{
    // 找到目标节点n，输出Yes并退出
    if (k == n)
    {
        cout << "Yes" << endl;
        exit(0); // 直接完全退出程序，避免后续执行
    }
    vis[k] = 1;
    for (int i : e[k])
    {
        // 仅访问：未被标记 + 节点值t[i]==0
        if (!vis[i] && t[i] == 0)
        {
            dfs(i); // 递归访问邻接节点，仅传i即可
        }
    }
}
void _()
{
    cin >> n >> m;
    t.resize(n + 1);
    e.resize(n + 1);
    vis.assign(n + 1, 0);
    // 第三步：读入节点值（存入全局t）
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i];
    }
    // 第四步：读入边（存入全局e）
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    if (t[1] == 0)
    {
        dfs(1);
    }
    // 若DFS未触发exit，说明无路径，输出No
    cout << "No" << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr), cout.tie(nullptr);
    int awa = 1;
    // cin >> awa;
    while (awa--)
    {
        _();
    }
    return 0;
}