题意：
有N 个局部联通的图。
Harry 和Sally 轮流从图中删边，删去一条边后，不与根节点相
连的部分将被移走。Sally 为先手。
图是通过从基础树中加一些边得到的。
所有形成的环保证不共用边，且只与基础树有一个公共点。
谁无路可走谁输
卡读题啊...$WA$了一节课了才发现是多组输入
树上删边游戏：叶子节点的SG值为0；中间节点的SG值为它的所有子节点的SG值加1 后的异或和。
一些节点多出去一个环？好像是Multi-SG唉！
奇环的后继状态，两条奇偶性相同的链，异或和一定没有1
偶环的后继状态，两条奇偶性不同的链，异或和一定没有0
然后就是非常恶心的找环啦
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; const int N=105,M=505; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,m; struct edge{int v,ne;}e[M<<1]; int cnt=1,h[N]; inline void ins(int u,int v){ e[++cnt]=(edge){v,h[u]};h[u]=cnt; e[++cnt]=(edge){u,h[v]};h[v]=cnt; } int vis[N],st[N],top,sg[N],mark[M<<1],circle[N]; void dfs(int u){ int &now=sg[u];//printf("dfs %d ",u); if(vis[u]){ int x=st[top--],cnt=1; while(x!=u) cnt++,circle[x]=1,x=st[top--];top++; if(cnt&1) now^=1; //printf("circle %d %d ",u,cnt); return; } vis[u]=1; st[++top]=u; for(int i=h[u];i;i=e[i].ne) if(!mark[i]){ mark[i]=mark[i^1]=1; dfs(e[i].v); if(!circle[e[i].v]) now^=sg[e[i].v]+1; } if(st[top]==u) top--; } int main(){ freopen("in","r",stdin); int S; while(scanf("%d",&S)!=EOF){ int sum=0; while(S--){ n=read();m=read(); for(int i=1;i<=n;i++) vis[i]=sg[i]=circle[i]=0; top=0; memset(mark,0,sizeof(mark)); cnt=1;memset(h,0,sizeof(h)); for(int i=1;i<=m;i++) ins(read(),read()); dfs(1); sum^=sg[1]; //printf("Sg ");for(int i=1;i<=n;i++) printf("%d ",sg[i]);puts(""); } if(sum) puts("Sally"); else puts("Harry"); } }