图的邻接矩阵 DFS 搜索模板

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

const int N = 1005;              // 根据题目点的数量范围调整
int g[N][N];                     // 邻接矩阵，g[u][v] = 1 表示有边
bool vis[N];
int n, m, st, ed, cnt;

void dfs(int u) {
    if (u == ed) { cnt++; return; }   // 到达终点计数
    for (int v = 1; v <= n; v++) {
        if (g[u][v] == 0 || vis[v]) continue;  // 无边或已访问
        vis[v] = 1;
        dfs(v);
        vis[v] = 0;                // 回溯撤销标记
    }
}

int main() {
    cin >> n >> m >> st >> ed;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u][v] = 1;      // 无权图
        // 无向图需要反向边
        // g[v][u] = 1;
    }

    vis[st] = 1;                  // 必须标记起点
    dfs(st);
    cout << cnt;
    return 0;
}