树的删边游戏。。
由于题目的特殊性，我们只需计算环的边数值。若为偶环，则直接把环的根节点置0。若为奇环，则留下一条边与根结点相连，并那它们的SG置0；
注意的是，两个点也可构成环，因为允许重边。所以，我们只需求点双连通分量，并判断分量中边的数量即可。然后DFS求树的SG值。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 6 using namespace std; 7 8 const int N=110; 9 const int M=1100; 10 int n,m; 11 struct { 12 int v,next; 13 }edge[M]; 14 struct { 15 int u,v; 16 }edge_stack[M],tmp; 17 int dfn[N],low[N],index; 18 int edge_top,tot; 19 bool vis[N],vis_e[M]; 20 int head[N],sg[N]; 21 22 void addedge(int u,int v){ 23 vis_e[tot]=false; 24 edge[tot].v=v; 25 edge[tot].next=head[u]; 26 head[u]=tot++; 27 } 28 29 void tarjan(int u){ 30 int i,j,k,v,e; 31 dfn[u]=low[u]=++index; 32 for(e=head[u];e!=-1;e=edge[e].next){ 33 v=edge[e].v; 34 if(dfn[v]==-1){ 35 vis_e[e]=vis_e[e^1]=true; 36 edge_stack[++edge_top].u=u; 37 edge_stack[edge_top].v=v; 38 tarjan(v); 39 low[u]=min(low[u],low[v]); 40 if(dfn[u]<=low[v]){ 41 int cnt=0; 42 do{ 43 tmp.u=edge_stack[edge_top].u; 44 tmp.v=edge_stack[edge_top].v; 45 edge_top--; 46 cnt++; 47 vis[tmp.u]=vis[tmp.v]=true; 48 // printf("edge=%d %d ",tmp.u,tmp.v); 49 }while(!(tmp.u==u&&tmp.v==v)); 50 // printf(" "); 51 if((cnt&1)){ 52 vis[tmp.u]=vis[tmp.v]=false; 53 } 54 else vis[tmp.u]=false; 55 } 56 } 57 else{ 58 if(!vis_e[e]){ 59 low[u]=min(low[u],dfn[v]); 60 if(dfn[u]>dfn[v]){ 61 edge_stack[++edge_top].u=u; 62 edge_stack[edge_top].v=v; 63 } 64 } 65 } 66 } 67 } 68 69 int dfs(int u){ 70 int e,v; 71 vis[u]=true; 72 int ans=sg[u]; 73 for(e=head[u];e!=-1;e=edge[e].next){ 74 int v=edge[e].v; 75 if(!vis[v]){ 76 ans^=(dfs(v)+1); 77 } 78 } 79 return ans; 80 } 81 82 int main(){ 83 int k,u,v; 84 while(scanf("%d",&k)!=EOF){ 85 int ans=0; 86 while(k--){ 87 edge_top=-1; 88 scanf("%d%d",&n,&m); 89 tot=index=0; 90 for(int i=1;i<=n;i++){ 91 vis[i]=false; sg[i]=0; 92 head[i]=dfn[i]=low[i]=-1; 93 } 94 for(int i=1;i<=m;i++){ 95 scanf("%d%d",&u,&v); 96 addedge(u,v); 97 addedge(v,u); 98 } 99 tarjan(1); 100 ans^=dfs(1); 101 } 102 if(ans) printf("Sally "); 103 else printf("Harry "); 104 } 105 return 0; 106 }