poj3710 Christmas Game

题目描述

题解：

树上删边。

对于奇数长度的环，可以看做一条边。

对于偶数长度的环，可以看做什么都没有。

没有特别好的解释……

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = ;

template<typename T>

inline void read(T&x)

{

    T f = ,c = ;char ch = getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){c=c*+ch-'';ch=getchar();}

    x = f*c;

}

int T,n,m,hed[N],cnt;

struct EG

{

    int to,nxt;

}e[*N];

void ae(int f,int t)

{

    e[++cnt].to = t;

    e[cnt].nxt = hed[f];

    hed[f] = cnt;

}

bool vis[N],cir[N],ban[*N];

int sta[N],tl;

int dfs(int u)

{

    vis[u]=;

    sta[++tl]=u;

    int ret = ;

    for(int j=hed[u];~j;j=e[j].nxt)

    {

        if(ban[j])continue;

        ban[j]=ban[j^]=;

        int to = e[j].to;

        int now;

        if(!vis[to])now=(dfs(to)+);

        else

        {

            int q = sta[tl--];

            while(q!=to)

            {

                cir[q]=;

                q=sta[tl--];

            }

            tl++;

            return ;

        }

        if(cir[to])ret^=(now&);

        else ret^=now;

    }

    return ret;

}

int main()

{

    while(scanf("%d",&T)>)

    {

//    read(T);

        int ans=;

        while(T--)

        {

            memset(hed,-,sizeof(hed));

            memset(cir,,sizeof(cir));

            memset(vis,,sizeof(vis));

            memset(ban,,sizeof(ban));

            cnt=-;tl=;

            read(n),read(m);

            for(int f,t,i=;i<=m;i++)

            {

                read(f),read(t);

                ae(f,t),ae(t,f);

            }

            int now = dfs();

            ans^=now;

        }

        puts(ans?"Sally":"Harry");

    }

    return ;

}