poj 2425 博弈 SG函数
scturtle
posted @ 2010年9月10日 03:26
in algorithm
, 2472 阅读
#include <cstdio> #include <cstring> #include <vector> std::vector<int> adj[1000]; int f[1000]; int n; int mex(int v) { bool g[1000]={0}; int i,w; for(i=0;i<adj[v].size();i++) { w=adj[v][i]; if(f[w]==-1) f[w]=mex(w); g[f[w]]=1; } for(i=0;;i++) if(!g[i]) return i; } int main() { #ifndef ONLINE_JUDGE freopen("in","r",stdin); freopen("out","w",stdout); #endif int m,v,w,sum; while(scanf("%d",&n)!=EOF) { for(v=0;v<n;v++) { adj[v].clear(); scanf("%d",&m); while(m--) { scanf("%d",&w); adj[v].push_back(w); } } memset(f,-1,sizeof(f)); while(scanf("%d",&m)!=EOF&&m) { sum=0; while(m--) { scanf("%d",&v); if(f[v]==-1) f[v]=mex(v); sum^=f[v]; } if(sum) puts("WIN"); else puts("LOSE"); } } return 0; }