HDOJ 1524 A Chess Game SG函数

//HDOJ 1524 A Chess Game SG函数
/*
题意：有一个有向无环图，在一些点有石子，这些石子每次可以往其后继结点移动。
	  两个人轮流移动，不能移动的为输

思路：建图，算出每个点的SG值
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define N 1005
#define M 1000005

int n,m;
int num,head[N];
int in[N],out[N],sg[N];

struct node{
	int from;
	int to;
	int next;
}edge[M];

void addedge(int from,int to){
	edge[num].from = from;
	edge[num].to = to;
	edge[num].next = head[from];
	head[from] = num++;
}

void init(){
	num = 0;
	memset(head,-1,sizeof(head));
	memset(sg,-1,sizeof(sg));
}

int mex(int n){
	int i;
	bool vis[N];
	if(sg[n] != -1)
		return sg[n];
	memset(vis,false,sizeof(vis));
	for(i = head[n]; i != -1; i = edge[i].next){
		if(sg[edge[i].to] == -1)
			sg[edge[i].to] = mex(edge[i].to);
		vis[sg[edge[i].to]] = true;
	}
	for(i = 0; ; ++i)
		if(vis[i]==false)
			return i;
}

int main(){
	int i,j,k,x,a,p;
	while(scanf("%d",&n)!=EOF){
		init();
		for(i = 0; i < n; ++i){
			scanf("%d",&m);
			for(j = 0; j < m; ++j){
				scanf("%d",&k);
				addedge(i,k);
			}
		}
		while(scanf("%d",&x),x){
			int ans = 0;
			for(i = 0; i < x; ++i){
				scanf("%d",&a);
				ans ^= mex(a);
			}
			puts(ans?"WIN":"LOSE");
		}
	}	
	return 0;
}