poj 3710 Christmas Game（博弈 无向图删边游戏）

游戏）"/>

poj 3710 Christmas Game（博弈 无向图删边游戏）

题目链接

贾志豪的论文里提到的经典题目，关于树的删边，没有环的情况下，有一个结论：每个节点的sg值的所有的子节点sg值加一的异或，叶子结点的sg值为0。

而这道题目中的树经过了特殊处理会有环的存在，但是保证环只会有一个点和树相连。

这里要用到The Fusion Principle（融合定理）：

将图中 任意一个偶环缩成一个新点，任意一个奇环缩成一个新点加新边；所有连到原来环上的边全都改成与新点相连。这样的改动不会影响图的sg值。

然后这里我们找出图中的强联通分量，这里用到了 Tarjan算法，我们可以用一个vis数组记录，对于一个强联通分量除了与树相连的那个点其余全部标记上，这样我们在求解sg的时候跳过这些点就可以达到目的。

对于出现的重边，我们可以记录边的个数，如果是偶数个，可以当成偶环处理，奇数则不用管。

以下代码，也是参照别人的博客写的。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include <cmath>
#include<iostream>
#include<algorithm>
#include <vector>
#include <bitset>
#define maxn 105
#define ll long long
#define MEM(x,num) memset(x,num,sizeof(x))using namespace std;vector<int> g[maxn];
int low[maxn],dfn[maxn];    //Tarjan的参量
bool vis[maxn];     //用来标记不需要的点
bool instack[maxn];
int s[maxn],top; //栈
int edge[maxn][maxn];   //判断有没有重边，如果是偶数个可以看成偶环来处理，即缩成一个点，奇数就可以保留。void init()
{int m,n;cin>>n>>m;for(int i=0; i<=n; i++)g[i].clear();MEM(dfn,0);MEM(low,0);MEM(vis,false);MEM(instack,false);MEM(edge,0);MEM(s,0);top=0;for(int i=0; i<m; i++){int a,b;cin>>a>>b;g[a].push_back(b);g[b].push_back(a);edge[a][b]++;edge[b][a]++;   //统计输入中边出现的次数}
}void Tarjan(int u,int fa,int depth)
{low[u]=dfn[u]=depth;s[top++]=u;instack[u]=true;for(int i=0; i<g[u].size(); i++){int v=g[u][i];if(v==fa){if(edge[u][v]>1&&edge[u][v]%2==0)vis[u]=true;continue;}if(!dfn[v]){Tarjan(v,u,depth+1);low[u]=min(low[u],low[v]);}else if(instack[v])low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u])  //这里表示u是这个环的连接点{int cnt=1;top--;while(s[top]!=u){vis[s[top--]]=true;     //将环中的其他点都标记掉，并计数cnt++;}if(cnt&&(cnt&1))  //如果环是奇数，则多保留一个点，就会多一条边vis[s[top+1]]=false;}
}int getsg(int u,int fa)
{int res=0;for(int i=0; i<g[u].size(); i++){int v=g[u][i];if(!vis[v]&&v!=fa)res^=(1+getsg(v,u));}return res;
}int main()
{int t;while(cin>>t){int res=0;while(t--){init();Tarjan(1,-1,1);res^=getsg(1,-1);}if(res) printf("Sally\n");else printf("Harry\n");}return 0;
}