二分图染色。。。。

Catch

2
3 3 0
0 1
0 2
1 2
2 1 0
0 1

Case 1: YES
Case 2: NO


Hint
For the first case, just look at the table below. (YES means the thief may appear at the cross at that moment)
 
For the second input, at any moment, there’s at least one cross that the thief can’t reach.
 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

const int maxn=110000;

struct Edge
{
    int to,next;
}edge[maxn*10];

int Adj[maxn],Size,n,m,s;
int color[maxn],fa[maxn];

void dsu_init()
{
    for(int i=0;i<n+10;i++) fa[i]=i;
}

int Find(int x)
{
    if(x==fa[x]) return fa[x];
    else return fa[x]=Find(fa[x]);
}

void Union(int a,int b)
{
    int A=Find(a),B=Find(b);
    if(A==B) return ;
    fa[A]=B;
}

void init()
{
    memset(color,-1,sizeof(color));
    memset(Adj,-1,sizeof(Adj));
    Size=0;
}

void Add_Edge(int u,int v)
{
    edge[Size].to=v;
    edge[Size].next=Adj[u];
    Adj[u]=Size++;
}

bool bfs(int x)
{
    queue<int> q;
    q.push(x);
    color[x]=0;

    while(!q.empty())
    {
        int u=q.front(); q.pop();

        for(int i=Adj[u];~i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(color[v]==-1)
            {
                color[v]=!color[u];
                q.push(v);
            }
            else
            {
                if(color[v]==color[u]) return false;
            }
        }
    }
    return true;
}

int main()
{
    int T_T,cas=1;
    scanf("%d",&T_T);
while(T_T--)
{
    printf("Case %d: ",cas++);
    scanf("%d%d%d",&n,&m,&s);
    init(); dsu_init();
    for(int i=0;i<m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        Add_Edge(u,v);
        Add_Edge(v,u);
        Union(u,v);
    }

    /// check connect
    int goal=Find(0);
    bool flag=true;
    for(int i=1;i<n;i++)
    {
        if(Find(i)!=goal)
        {
            printf("NO\n");
            flag=false; break;
        }
    }
    if(flag==false) continue;

    ///got color
    if(bfs(s)) puts("NO");
    else puts("YES");
}
    return 0;
}

HDOJ 3478 Catch,布布扣,bubuko.com

HDOJ 3478 Catch

原文：http://blog.csdn.net/u012797220/article/details/20959147