$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路： 求出所有棋子的 sg 函数值的异或值，若为0，则先手必败，否则先手必胜

SG函数证明可参考： 集合-Nim游戏

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 2010, M = 6010;

int n,m,k;
int h[N],e[M],ne[M],idx;
int f[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int sg(int u)
{
    if(f[u]!=-1) return f[u];

    //将能到达的点的 sg 函数值放入集合
    set<int> S;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        S.insert(sg(j));
    }

    //找到集合中不存在的最小自然数
    for(int i=0;;i++)
        if(!S.count(i))
            return f[u]=i;
}

int main()
{
    cin>>n>>m>>k;

    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    memset(f,-1,sizeof f);

    int res=0;
    for(int i=0;i<k;i++)
    {
        int u;
        cin>>u;
        res^=sg(u);
    }

    if(res) puts("win");
    else puts("lose");

    return 0;
}