知识储备：
解决办法（奇偶去环）：
（1） 对于长度为奇数的环，去掉其中任意一个边之后，剩下的
两个链长度同奇偶，抑或之后的 SG 值不可能为奇数，所
以它的 SG 值为 1；
（2） 对于长度为偶数的环，去掉其中任意一个边之后，剩下的
两个链长度异奇偶，抑或之后的 SG 值不可能为 0，所以它
的 SG 值为 0；
#include<stdio.h> #include<string.h> #include<algorithm> #include<vector> using namespace std; vector<int>edge[105]; //邻接表 int mat[105][105]; //存放边的数量 int low[105],dfa[105]; //Tarjan参量 int s[105],top; //堆栈 bool instack[105]; bool vis[105]; //在Tarjan找环之后，把不需要的点标记掉 void Tarjan(int u,int pre,int depth) { low[u]=dfa[u]=depth; s[top++]=u; instack[u]=true; for(int i=0; i<edge[u].size(); i++) { int v=edge[u][i]; if(v==pre&&mat[u][v]>1) //判断重边 { if(mat[u][v]%2==0) vis[u]=true; continue; } if(!dfa[v]) { Tarjan(v,u,depth+1); low[u]=min(low[u],low[v]); } else if(v!=pre&&instack[v]) low[u]=min(low[u],dfa[v]); } if(dfa[u]==low[u]) { int cnt=1; top--; while(s[top]!=u) { vis[s[top--]]=true; cnt++; } if(cnt&&(cnt&1)) //如果节点为奇数，则保留一个点，包括u，也就是两个点，保留一条边 vis[s[top+1]]=false; } } int get_sg(int u,int pre) { int ret=0; for(int i=0; i<edge[u].size(); i++) { int v=edge[u][i]; if(!vis[v]&&v!=pre) ret^=(1+get_sg(v,u)); } return ret; } int main() { int k,n,m; while(scanf("%d",&k)!=EOF) { int ret=0; while(k--) { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) edge[i].clear(); memset(mat,0,sizeof(mat)); memset(low,0,sizeof(low)); memset(dfa,0,sizeof(dfa)); memset(instack,false,sizeof(instack)); memset(vis,false,sizeof(vis)); top=0; while(m--) { int u,v; scanf("%d%d",&u,&v); mat[u][v]++; mat[v][u]++; edge[u].push_back(v); edge[v].push_back(u); } Tarjan(1,-1,1); ret^=get_sg(1,-1); } puts(ret?"Sally":"Harry"); } return 0; }