题解

Writer: Yue_chen

题意

$n$ 个点，$m$ 条有向边，从点 $1$ 出发，每次走一条没走过的边，可以随时结束，问有多少种走法。

分析

题目的 $n$ 虽然大的惊人，但是 $m$ 却小的可怜。

无需考虑优化，我们将之前走过的边记录下来，每次暴力枚举 $m$ 次，找一条没走过的边去走，用dfs去考虑第 $i$ 天走哪条边，vis数组去记录那些边是前 $i$ 天走过的，方法比较经典。

代码

using namespace std;

using i64 = long long;

void solve() {
	int n, m; cin >> n >> m;

    //存边，array<int,2> = pair<int,int> = 两个int
    vector<array<int,2>> e(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> e[i][0] >> e[i][1];
    }
    
    vector<int> vis(m + 1);
  //局部内函数写法，看不懂的在函数外面正常写就行
    function<int(int)> dfs = [&](int u) {
        int ans = 1;
        for (int i = 1; i <= m; i++) {
            if (e[i][0] == u and !vis[i]) {
                vis[i] = 1;
                ans += dfs(e[i][1]);
                vis[i] = 0;
            }
        } return ans;
    };
    cout << dfs(1) << "\n";
}

signed main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	int t = 1;// cin>>t;
	while (t--) solve();
	return 0;
}