dfs找所有路径

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

// 全局变量说明：
// t = 终点
// adj = 邻接表，adj[u] 存储与 u 相邻的所有顶点
// vis = 标记数组，防止路径中重复访问同一顶点（避免走回头路）
// path = 当前 DFS 正在走的路径
// record = 存储所有从 s 到 t 的路径
int t;
vector<vector<int> > adj;
vector<bool> vis;
vector<int> path;
vector<vector<int> > record;

// 深度优先搜索，寻找从 u 到 t 的所有简单路径
void dfs(int u) {

    // 如果当前点 u 就是目标点 t
    // 说明 path 保存了一条完整路径
    if (u == t) {
        record.push_back(path);   // 把当前整条路径保存下来
        return;                   // 返回上一层继续搜索别的路径
    }

    // 枚举从 u 出发的所有邻接点 v
    for (int i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i];

        // 如果 v 未在当前路径中出现（避免重复）
        if (!vis[v]) {

            // 选择：走向 v
            vis[v] = true;        // 标记 v 已经在当前路径中
            path.push_back(v);    // 把 v 加入路径

            dfs(v);               // 递归搜索从 v 出发的所有路径

            // 回溯：撤销选择
            vis[v] = false;       // 取消标记，允许其他路径再次访问 v
            path.pop_back();      // 从当前路径中弹出 v
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    cin >> n >> m >> s >> t;   // 输入点数、边数、起点 s 和终点 t

    adj.resize(n + 1);         // 邻接表初始化为 n 个点（1 开始编号）
    vis.resize(n + 1);         // 访问标记初始化为 n 个点（默认全为 false）

    // 输入图的边（无向图：双向加入邻接表）
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);   // u → v
        adj[v].push_back(u);   // v → u
    }

    // 初始化 DFS 起点
    path.push_back(s);         // 路径中加入起点
    vis[s] = true;             // 起点标记为已访问
    dfs(s);                    // 从 s 出发进行深度优先搜索

    // 输出所有找到的路径
    for (int i = 0; i < record.size(); ++i) {
        for (int j = 0; j < record[i].size(); ++j) {
            cout << record[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}