POJ3710 Christmas Game 博弈论 sg函数树的删边游戏

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

叶子节点的 SG 值为0；中间节点的SG值为它的所有子节点的SG值加1后的异或和。

偶环可以视作一个点，奇环视为一条边（连了两个点）。

这道题有两个需要注意的地方，这道题是多样例测试和这道题中两点之间形成的环要特判。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<iostream>

 #include<map>

 #include<ctime>

 using namespace std;

 const int maxn=;

 int n;

 struct nod{

     int y,next;

 }e[maxn*];

 int head[maxn]={},tot;

 int dep[maxn]={},low[maxn]={},cnt;

 int wtf[maxn][maxn]={};

 int sta[maxn]={},top=;

 int f[maxn]={};

 void init(int x,int y){

     e[++tot].y=y;e[tot].next=head[x];head[x]=tot;

 }

 void dfs(int x,int fa){

     int y;dep[x]=low[x]=++cnt;sta[++top]=x;

     for(int i=head[x];i;i=e[i].next){

         y=e[i].y;

         if(y==fa){continue;}

         if(wtf[x][y]!=){continue;}

         if(dep[y]){

             low[x]=min(low[x],low[y]);

         }else{

             dfs(y,x);

             low[x]=min(low[x],low[y]);

         }

     }

     if(low[x]==dep[x]){

         int z=;

         do{

             z++;top--;

         }while(sta[top+]!=x);

         if(z>){

             if(z&){

                 f[x]=;

             }

         }

         for(int i=head[x];i;i=e[i].next){

             y=e[i].y;

             if(y==fa){continue;}

             if(wtf[x][y]!=){continue;}

             f[x]^=(f[y]+);

         }

     }

 }

 int main(){

     while(~scanf("%d",&n)){

         int m,k;

         int ans=,x,y;

         for(int i=;i<=n;i++){

             memset(head,,sizeof(head));

             memset(dep,,sizeof(dep));

             memset(low,,sizeof(low));

             memset(wtf,,sizeof(wtf));

             memset(f,,sizeof(f));

             tot=;cnt=;

             scanf("%d%d",&m,&k);

             for(int i=;i<=k;i++){

                 scanf("%d%d",&x,&y);

                 init(x,y);init(y,x);

                 wtf[x][y]++;wtf[y][x]++;

             }dfs(,);

             ans^=f[];

         }

         if(!ans)printf("Harry\n");

         else printf("Sally\n");

     }

     return ;

 }