HDOJ 1524 A Chess Game SG函數

[cpp]
//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; 
}