HDU - 3478 Catch（判奇环/二分图）

时间：2023-03-09 16:01:50
HDU - 3478 Catch（判奇环/二分图）

http://acm.hdu.edu.cn/showproblem.php?pid=3478

题意

给一个无向图和小偷的起点，小偷每秒可以向相邻的点出发，问有没有一个时间点小偷可能出现在任何点。

分析

首先图得要是联通的，由于是无向的，那么只需记录图中是否存在悬挂点（度为0），存在的话就不联通了，输出NO。只要图是二分图，小偷就不可能在某一时刻可能出现在任意位置，因为如果是二分图，在移动时必然是从一类结点走向另一类，这样任何时刻都存在一个走不到的点。于是用染色法判断是否为二分图即可。此外，还有判断奇环的做法，实质上就是二分图的性质，一个二分图中存在的环只能是偶环，具体证明可以自己推推。

#include<iostream>

#include<cmath>

#include<cstring>

#include<queue>

#include<vector>

#include<cstdio>

#include<algorithm>

#include<map>

#include<set>

#define rep(i,e) for(int i=0;i<(e);i++)

#define rep1(i,e) for(int i=1;i<=(e);i++)

#define repx(i,x,e) for(int i=(x);i<=(e);i++)

#define X first

#define Y second

#define PB push_back

#define MP make_pair

#define mset(var,val) memset(var,val,sizeof(var))

#define scd(a) scanf("%d",&a)

#define scdd(a,b) scanf("%d%d",&a,&b)

#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)

#define pd(a) printf("%d\n",a)

#define scl(a) scanf("%lld",&a)

#define scll(a,b) scanf("%lld%lld",&a,&b)

#define sclll(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)

#define IOS ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

typedef long long ll;

template <class T>

void test(T a){cout<<a<<endl;}

template <class T,class T2>

void test(T a,T2 b){cout<<a<<" "<<b<<endl;}

template <class T,class T2,class T3>

void test(T a,T2 b,T3 c){cout<<a<<" "<<b<<" "<<c<<endl;}

const int inf = 0x3f3f3f3f;

const ll INF = 0x3f3f3f3f3f3f3f3fll;

const ll mod = ;

int T;

void testcase(){

    printf("Case %d: ",++T);

}

const int MAXN = 1e6+;

const int MAXM = ;

struct node{

    int v,nxt;

}e[MAXN*];

int head[*MAXN],deg[MAXN],color[MAXN],n,m,cnt;

void init(){

    mset(head,-);

    mset(deg,);

    mset(color,);

    cnt=;

}

void addEdge(int u,int v){

    e[cnt].v=v;

    e[cnt].nxt=head[u];

    head[u]=cnt++;

}

int bfs(int rt){

    color[rt]=;

    queue<int> que;

    que.push(rt);

    while(!que.empty()){

        int u = que.front();

        que.pop();

        for(int i=head[u];~i;i=e[i].nxt){

            int v = e[i].v;

            if(color[v]==color[u]) return ;

            if(!color[v]){

                color[v]=-color[u];

                que.push(v);

            }

        }

    }

    return ;

}

int main() {

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif // LOCAL

    int t,s,u,v;

    scd(t);

    T=;

    while(t--){

        scddd(n,m,s);

        init();

        for(int i=;i<m;i++){

            scdd(u,v);

            addEdge(u,v);

            addEdge(v,u);

            deg[u]++,deg[v]++;

        }

        int f=;

        for(int i=;i<n;i++){

            if(!deg[i]){

                f=;

                break;

            }

        }

        testcase();

        if(f){

            puts("NO");

            continue;

        }

        if(bfs()) puts("YES");

        else puts("NO");

    }

    return ;

}

相关文章