#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>

using namespace std;
#define maxn 110
int mat[maxn][maxn];
int m,stk[maxn],top;
bool sign[maxn],incir[maxn];

int dfs(int u)
{
	int cntr = 0;
	for(int i=1;i<=m;i++)
	{
		if(mat[u][i] > 0)
		{
			int tmp = 0;
			mat[i][u]--,mat[u][i]--;
			if(sign[i] == 0)
			{
				sign[i] = 1;
				stk[top++] = i;
				tmp = dfs(i) + 1;
			}
			else
			{
				while(top > 0 && stk[top - 1] != i)
					incir[stk[--top]] = 1;
				return 1;
			}
			if(incir[i])
				cntr ^= (tmp % 2);
			else
				cntr ^= tmp;
		}
	}
	//if(top > 0 && incir[top - 1] == 0)
	//	top--;
	return cntr;
}
int getsg()
{
	for(int i=1;i<=m;i++)
		sign[i] = 0,incir[i] = 0;
	top = 1;
	stk[0] = 1;
	sign[1] = 1;
	return dfs(1);
}
int main()
{
    int n,anssg;
    while(scanf("%d",&n)!=EOF)
    {
		anssg = 0;
		int k;
		while(n--)
		{
			scanf("%d %d",&m,&k);
			memset(mat,0,sizeof(mat));
			int a,b;
			while(k--)
			{
				scanf("%d %d",&a,&b);
				mat[a][b]++;
				mat[b][a]++;
			}
			anssg ^= getsg();
		}
		if(anssg)
			printf("Sally\n");
		else printf("Harry\n");

    }
    return 0;
}

这个是我写的一个AC的程序，但是如果加上，if(top > 0 && incir[top - 1] == 0)  	top--;这一点程序就是WA,按照我的理解，每个环上的节点都应该出栈，每个树上的节点也应该出栈，但是如果注释掉这一句的话，一些树上的节点就可能被标记到环中去了。

• Re:这道题是不是有错误？ (16) YaphetS 2013-02-18 23:34:11