有向图游戏 SG函数【博弈论】C++

SG函数可以用来判断在一个给定的有向图游戏中，当前局面的胜负状态。

SG函数的定义如下：
设当前节点为v，那么SG(v)为当前局面的SG值。SG(v)的定义如下：
- 如果当前节点v没有后继节点，则SG(v) = 0
- 如果当前节点v有若干个后继节点，分别为v1,v2,...,v_n，那么SG(v)为所有后继节点的SG值的异或和。即：SG(v) = SG(v1) XOR SG(v2) XOR ... XOR SG(v_n)

根据SG函数的定义，可以得出以下结论：
- 如果SG(v)为0，则当前局面为必败态（先手必输）；
- 如果SG(v)不为0，则当前局面为必胜态（先手必胜）；
- SG函数具有性质：SG(v) = SG(w)，当且仅当v和w的后继节点的SG值相同。

需要注意的是，有向图游戏中的SG函数只适用于无环图。对于有环图，SG函数的定义需要进一步扩展。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
// #define int long long
#define endl "\n"
#define KUI ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
const int con = 2e5 + 4;
const int mod = 998244353;
int n, m, k, f[con];
vector<int> v[con];
int sg(int u)
{if (f[u] != -1){return f[u];}set<int> s;for (auto x : v[u]){s.insert(sg(x));}int ans = 0;while (1){if (s.count(ans) == 0){return f[u] = ans;}ans++;}
}
void take()
{cin >> n >> m >> k;for (int i = 1; i <= m; i++){int a1, a2;v[a1].push_back(a2);}memset(f, -1, sizeof f);int res = 0;int x;for (int i = 1; i <= k; i++){cin >> x;res ^= sg(x);}if (res > 0){cout << "先手必胜" << endl;}else{cout << "后手必胜" << endl;}
}
signed main()
{KUI;int t1 = 1;while (t1--){take();}return 0;
}