首页 > 代码库 > POJ 3710

POJ 3710

2024-07-08 06:55:01   218人阅读

树的删边游戏。。

由于题目的特殊性，我们只需计算环的边数值。若为偶环，则直接把环的根节点置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("\n"); 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\n");103         else printf("Harry\n");104     }105     return 0;106 }
View Code

 


联系
我们