HDU Catch （二分图判断奇环+并查集判断联通）

//
#include<bits/stdc++.h>
using namespace std;
#define maxnn 2000110
int n,m,s;
int las[maxnn],nex[maxnn],tot,en[maxnn],col[maxnn],fla=0;
int f[maxnn];
int T;
int  gf(int v)
{
    return f[v]==v?v:f[v]=gf(f[v]);
}
void add(int a,int b)
{
    en[++tot]=b;
    nex[tot]=las[a];
    las[a]=tot;
}
void erfen(int v,int num)
{
    col[v]=num;
    if(fla==1) return ;
    for(int i=las[v];i;i=nex[i])
    {
        int y=en[i];
        if(col[y]==col[v])
        {
            fla=1;
            return ;
        }
        if(!col[y])
        {
            erfen(y,-num);
        }
     } 
     return ;
}
int main()
{
    int x,y,z;
    cin>>T;
    int tot=0;
    while(T--)
    {
        tot++;
        scanf("%d%d%d",&n,&m,&s);
        memset(las,0,sizeof(las));
        memset(col,0,sizeof(col));
        int sec=n;
        for(int i=0;i<n;i++)
            f[i]=i;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
            if(gf(x)!=gf(y))
            {
                f[gf(x)]=gf(y);
                sec--;
            }
        }
        if(sec!=1)
        {
            printf("Case %d: ",tot);
            printf("NO\n");
            continue;
        }
        fla=0;
        erfen(s,1);
        printf("Case %d: ",tot);
        if(fla==1)
            printf("YES\n");
        else
            printf("NO\n");
    }
}