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

#include<bits/stdc++.h>
using namespace std;
const int N=1001;
int sg[N],n;
vector<int>p[N];
int dfs(int now)
{
    if(sg[now]!=-1) return sg[now];
    bool vis[1001]={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()
{
    while(scanf("%d",&n)!=EOF)
	{
        memset(sg,-1,sizeof(sg));
        for(int i=0;i<n;i++)
		{
            int a;scanf("%d",&a);
            p[i].clear();
            for(int j=0,x;j<a;j++)
			{
                scanf("%d",&x);
                p[i].push_back(x);//每个棋子都是孤立的，𝑘 个棋子拆分成 𝑘 个有向图游戏,利用 SG 定理判断即可
            }
        }
        int q;
        while(scanf("%d",&q)&&q)
		{
            int ans=0;
            for(int i=0,x;i<q;i++)
			{
                scanf("%d",&x);
                ans^=dfs(x);
            }
            puts(ans?"WIN":"LOSE");
        }
    }
    return 0;
}