poj 3710 Christmas Game 博弈论

思路：首先用Tarjan算法找出树中的环，环为奇数变为边，为偶数变为点。

之后用博弈论的知识：某点的SG值等于子节点+1后的异或和。

代码如下：

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<vector>

 #include<cstring>

 using namespace std;

 int ans;

 vector<int>p[];

 bool vis[],inss[];

 int low[],dfa[],num[][],ss[],top;

 void Tarjan(int u,int pre,int d)

 {

     low[u]=dfa[u]=d;

     ss[top++]=u;

     inss[u]=;

     for(int i=;i<p[u].size();i++){

         int v=p[u][i];

         if(v==pre&&num[u][v]>){

             if(num[u][v]%==) vis[u]=;

             continue;

         }

         if(!dfa[v]){

             Tarjan(v,u,d+);

             low[u]=min(low[u],low[v]);

         }

         else if(v!=pre&&inss[v]){

             low[u]=min(low[u],dfa[v]);

         }

     }

     if(low[u]==dfa[u]){

         top--;

         int cnt=;

         while(ss[top]!=u){

             vis[ss[top--]]=;

             cnt++;

         }

         if(cnt&) vis[ss[top+]]=;

     }

 }

 int dfs(int d,int pre)

 {

     int ans=;

     for(int i=;i<p[d].size();i++){

         if(p[d][i]!=pre&&!vis[p[d][i]])

             ans^=(+dfs(p[d][i],d));

     }

     return ans;

 }

 int main()

 {

     int n,m,a,b,t,ans;

     while(scanf("%d",&t)!=EOF){

         ans=;

         while(t--){

             memset(vis,,sizeof(vis));

             memset(ss,,sizeof(ss));

             memset(low,,sizeof(low));

             memset(dfa,,sizeof(dfa));

             memset(num,,sizeof(num));

             memset(inss,,sizeof(inss));

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

             for(int i=;i<=n;i++) p[i].clear();

             while(m--){

                 scanf("%d%d",&a,&b);

                 num[a][b]++;

                 num[b][a]++;

                 p[a].push_back(b);

                 p[b].push_back(a);

             }

             top=;

             Tarjan(,-,);

             ans^=dfs(,-);

         }

         puts(ans?"Sally":"Harry");

     }

     return ;

 }