Poj Solution 2425

http://poj.org/problem?id=2425

#include <vector> 
#include <iostream>
using namespace std;
vector<int> edges[1000];
int N,M,GS[1000],ans;
 
int DFS(int n) /* 典型求 SG 函数的办法 */
{
    if(GS[n]!=-1) return GS[n];
    bool used[1000];
    memset(used,0,sizeof(used));
    for(int i=0;i<edges[n].size();i++)
    {
        used[DFS(edges[n][i])]=true;
    }
    int i=0;
    while(used[i]) i++;
    return GS[n]=i;
}
 
int main()
{
    int num,next;
    while(scanf("%d",&N)!=EOF)
    {
        for(int i=0;i<N;i++)
        {
            edges[i].clear();
            scanf("%d",&num);
            for(int j=0;j<num;j++)
            {
                scanf("%d",&next);
                edges[i].push_back(next);
            }
        }
        memset(GS,-1,sizeof(GS));
        while(scanf("%d",&M)&&M)
        {
            ans=0;
            for(int i=0;i<M;i++) scanf("%d",&next),ans^=DFS(next);
            if(ans) printf("WINn");
            else printf("LOSEn");
        }
    }
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *