学步园

题意：R & B（还是alice和bob吧）进行无向图（点n<=10 边m<=30）上的博弈，所有边都是无色的，alice先开始找到任意无色边染成红色，bob把任意无色边
         染成蓝色，bob赢的条件是无向图中存在一颗完全由蓝色边组成的生成树，问bob是否有必胜策略。
题解：如果图中存在两个没有相交边组成的生成树，那么bob有必胜策略。

Sure原创，转载请注明出处。

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <set>
using namespace std;
const int maxn = 12;
const int maxe = 62;
struct node
{
    int v,id,next;
}edge[maxe];
int head[maxn],father[maxn];
set <int> hash;
int m,n,idx;

void init()
{
    memset(head,-1,sizeof(head));
    hash.clear();
    idx = 0;
    return;
}

int find(int u)
{
    return (u == father[u]) ? father[u] : (father[u] = find(father[u]));
}

void addedge(int u,int v,int ii)
{
    edge[idx].v = v;
    edge[idx].id = ii;
    edge[idx].next = head[u];
    head[u] = idx++;

    edge[idx].v = u;
    edge[idx].id = ii;
    edge[idx].next = head[v];
    head[v] = idx++;
    return;
}

void read()
{
    int u,v;
    for(int i=0;i<m;i++)
    {
        scanf("%d %d",&u,&v);
        addedge(u,v,i);
    }
    return;
}

bool check(int st)
{
    int cnt = n;
    for(int i=0;i<n;i++)
    {
        father[i] = i;
    }
    for(int i=0;i<idx;i+=2)
    {
        if((st & (1 << edge[i].id)) == 0)
        {
            int u = edge[i^1].v;
            int v = edge[i].v;
            u = find(u);
            v = find(v);
            if(u != v)
            {
                father[u] = v;
                cnt--;
            }
        }
    }
    return (cnt == 1);
}

bool dfs(int nodest,int edgest)
{
    if(check(edgest) == false) return false;  //并查集判断剩下的图是否连通
    if(nodest == (1 << n) - 1) return true;
    if(hash.find(edgest) != hash.end()) return false;  //判断当前状态是否搜索过
    hash.insert(edgest);
    for(int i=0;i<n;i++)
    {
        if(nodest & (1 << i))
        {
            for(int j=head[i];j != -1;j=edge[j].next)
            {
                if((nodest & (1 << edge[j].v)) == 0 && (edgest & (1 << edge[j].id)) == 0)
                {
                    if(dfs(nodest | (1 << edge[j].v) , edgest | (1 << edge[j].id))) return true;
                }
            }
        }
    }
    return false;
}

int main()
{
    while(scanf("%d %d",&n,&m))
    {
        if(n == -1 && m == -1) break;
        init();
        read();
        puts(dfs(1,0) ? "YES" : "NO");
    }
    return 0;
}