POJ 3710 Christmas Game (Tarjan求连通分量+树形博弈删边游戏)

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

题目：有多棵树进行删边博弈，注意这里的”树“可能存在环，形状也许是非常诡异的。

我们利用The Fusion Principle：任何环内的节点可以融合成一点而不会改变图的sg值。（下面我们称它为融合原则）

<wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>融合原则允许我们把任意一个根图简化为一个等效的可以通过冒号原则（即Colon Principle）简化为竹竿的树。

我们会发现，拥有奇数条边的环可简化为一条边，偶数条边的环可简化为一个节点。

在这一步中很明显要求我们能找到图中的环，而且判断环中节点的个数，进行处理。

利用Tarjan算法找出强连通分量，毕竟不是搞图论的，现学现用。。。理解不深

可能出现重边，对于重边的处理是，如果两点间有偶数条边，则当作偶数环处理，将其化为一个点，否则保留。

将图转化成我们所要的树之后，便是经典的删边游戏了。

叶子节点的SG值为0；中间节点的SG值为它的所有子节点的SG值加1 后的异或和。

最后把多棵树一起做 一次NIM便完成。

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#define C    240
#define TIME 10
#define inf 1<<25
#define LL long long
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;
}