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

新版代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
vector<int> G[N];
int f[N];

int sg(int x)
{
    // 记忆化搜索
    if (f[x] != -1)return f[x];
    // 把子节点的sg值插入集合
    set<int> S;
    for (int y : G[x]) S.insert(sg(y));
    // mex运算求当前节点的sg值并记忆
    for (int i = 0;; i++)
        if (!S.count(i))
            return f[x] = i;
}
int main()
{
    int n, m, k; scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, x, y; i <= m; i++)
        scanf("%d%d", &x, &y), G[x].push_back(y);
    memset(f, -1, sizeof f);
    int res = 0;
    for (int i = 1, x; i <= k; i++)
        scanf("%d", &x), res ^= sg(x);
    if (res)
        puts("win");
    else
        puts("lose");
    return 0;
}

旧版代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2001;
int sg[N], n, m, k;
vector<int> p[N];
int dfs(int now)
{
    if (sg[now] != -1) return sg[now];
    bool vis[N] = { 0 };
    for (int i = 0; i < p[now].size(); i++)
        vis[dfs(p[now][i])] = 1;
    int i = 0;
    while (vis[i]) i++;
    return sg[now] = i;
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    memset(sg, -1, sizeof(sg));
    for (int i = 1, x, y; i <= m; i++)
    {
        scanf("%d%d", &x, &y); x--; y--;
        p[x].push_back(y);
    }
    int ans = 0;
    for (int i = 1, x; i <= k; i++)
    {
        scanf("%d", &x); x--;
        ans ^= dfs(x);
    }
    puts(ans ? "win" : "lose");
    return 0;
}

G60 有向图游戏 SG函数【博弈论】
新版代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
vector<int> G[N];
int f[N];

int sg(int x) { // 记忆化搜索 if (f[x] != -1)return f[x]; // 把子节点的sg值插入集合 set<int> S; for (int y:G[x])S.insert(sg(y)); // mex运算求当前节点的sg值并记忆 for (int i = 0; ; i++) if (!S.count(i)) return f[x] = i; } int main() { int n,m,k;scanf("%d%d%d", &n, &m, &k); for (int i = 1,x,y; i <= m; i++) scanf("%d%d", &x, &y), G[x].push_back(y); memset(f, -1, sizeof f); int res = 0; for (int i = 1,x; i <= k; i++) scanf("%d", &x), res ^= sg(x); if (res) puts("win"); else puts("lose"); return 0; }</pre>

旧版代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2001;
int sg[N],n,m,k;
vector<int>p[N];
int dfs(int now)
{
    if(sg[now]!=-1) return sg[now];
    bool vis[N]={0};
    for(int i=0;i<p[now].size();i++)
        vis[dfs(p[now][i])]=1;
    int i=0;
    while(vis[i]) i++;
    return sg[now]=i;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    memset(sg,-1,sizeof(sg));
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);x--,y--;
        p[x].push_back(y);
    }
    int ans=0;
    for(int i=1,x;i<=k;i++)
    {
        scanf("%d",&x);x--;
        ans^=dfs(x);
    }
    puts(ans?"win":"lose");
    return 0;
}