POJ3710

想了好久终于搞定了，无向图删边游戏，但是会有环，对于环，很明显，如果是奇数环，所有后继SG值都会是偶数，所以这个状态SG为1，把环缩成一个点+1条边，如果是偶数环，那么后继SG非0，此环SG=1，就将环缩为1个点，对于环，利用tarjan+栈预处理下，就行了

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
vector<int>vt[110];
int n,m,k,a,b,cnt,dfn[110],lm[110],vi[110],mp[110][110];
int s[110],top;
void tarjan(int x,int fa)
{
	dfn[x]=lm[x]=++cnt;
	s[++top]=x;
	for(int i=0;i<vt[x].size();i++)
	{
		int y=vt[x][i];
		if(y==fa)
		{
			if(mp[x][y]%2==0)
				vi[x]=1;
			continue;
		}
		else
			if(!dfn[y])
			{
				tarjan(y,x);
				lm[x]=min(lm[x],lm[y]);
			}
			else
			{
				lm[x]=min(lm[x],dfn[y]);
			}
	}
	if(dfn[x]==lm[x])
	{
		int cnt=1;
		while(s[top]!=x)
		{
			vi[s[top--]]=1;//环所有点全去掉
			cnt++;
		}
		if(cnt!=1&&(cnt&1))
			vi[s[top+1]]=0;//奇数环多保留一个点.
		top--;//退栈。。
	}
}
int dfs(int x,int fa)
{
	int ans=0;
	for(int i=0;i<vt[x].size();i++)
	{
		int y=vt[x][i];
		if(y!=fa&&!vi[y])
			ans^=(dfs(y,x)+1);
	}
	return ans;
}
int main()
{
	while(~scanf("%d",&n))
	{
		int ans=0;
		while(n--)
		{
			cnt=top=0;
			memset(vi,0,sizeof(vi));
			memset(mp,0,sizeof(mp));
			memset(dfn,0,sizeof(dfn));
			scanf("%d%d",&m,&k);
			for(int i=1;i<=m;i++)
				vt[i].clear();
			for(int i=0;i<k;i++)
			{
				scanf("%d%d",&a,&b);
				vt[a].push_back(b);
				vt[b].push_back(a);
				mp[a][b]++;
				mp[b][a]++;
			}
			tarjan(1,0);
			ans^=dfs(1,0);
		}
		printf("%s\n",ans?"Sally":"Harry");
	}
	return 0;
}