【判断二分图】C. Catch

https://www.bnuoj.com/v3/contest_show.php?cid=9154#problem/C

【题意】

给定一个无向图，给定小偷的起始位置
从这个起始位置开始，小偷可以在单位时间内逃到相邻的点
问是否存在某一时刻，小偷可能到达这个无向图的任意点

【思路】

首先这个无向图必须是连通的
如果小偷能够在某一奇数步到达某一点，那么他可以在任意奇数步到达这一点；偶数步同理
如果这个图是一个二分图（即奇数步到达的点在一个集合，偶数步到达的点在一个集合），那么对于任意时刻（不是奇数步就是偶数步），小偷不可能到达这个图的任意点（只能是所有的奇数点或偶数点）
如果这个图不是二分图（等价于图中存在一个奇环），则我们可以找到一个点可以在奇数步到达，也可以在偶数步到达；进一步，以这个点为出发点，其他的所有点也都可以染相反的颜色。即只要图中有一个奇环，这个图的任意点就是可以是0，也可以是1。
某一时刻，小偷可能到达这个无向图的任意点等价于这个图连通且不是二分图。

【Accepted】

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<string>
  5 #include<cmath>
  6 #include<algorithm>
  7 #include<queue>
  8 using namespace std;
  9 const int maxn=1e5+3;
 10 const int maxm=5e5+3;
 11 int n,m,s;
 12 struct edge
 13 {
 14     int to;
 15     int nxt;
 16 }e[maxm];
 17 int tot;
 18 int head[maxn];
 19 int col[maxn];
 20 bool vis[maxn];
 21 void init()
 22 {
 23     tot=0;
 24     memset(head,-1,sizeof(head));
 25     memset(vis,false,sizeof(vis));
 26     memset(col,0,sizeof(col));
 27 }
 28 void add(int u,int v)
 29 {
 30     e[tot].to=v;
 31     e[tot].nxt=head[u];
 32     head[u]=tot++;
 33 }
 34 
 35 bool BFS(int u)
 36 {
 37     int cnt=0;
 38     queue<int> Q;
 39     Q.push(u);
 40     vis[u]=true;
 41     cnt++;
 42     while(!Q.empty())
 43     {
 44         u=Q.front();
 45         Q.pop();
 46         for(int i=head[u];i!=-1;i=e[i].nxt)
 47         {
 48             int v=e[i].to;
 49             if(!vis[v])
 50             {
 51                 vis[v]=true;
 52                 cnt++;
 53                 Q.push(v);                
 54             }
 55          } 
 56     }
 57     if(cnt==n)
 58     {
 59         return true;
 60     }
 61     else
 62     {
 63         return false;    
 64     }
 65 }
 66 bool Color(int u)
 67 {
 68     queue<int> Q;
 69     Q.push(s);
 70     while(!Q.empty())
 71     {
 72         u=Q.front();
 73         Q.pop();
 74         for(int i=head[u];i!=-1;i=e[i].nxt)
 75         {
 76             int v=e[i].to;
 77             if(!col[v])
 78             {
 79                 col[v]=!col[u];
 80                 Q.push(v);
 81             }
 82             else if(col[v]==col[u])
 83             {
 84                 return false;
 85             }
 86         }
 87      } 
 88      return true;
 89 }
 90 int main()
 91 {
 92     int cas=0;
 93     int T;
 94     scanf("%d",&T);
 95     while(T--)
 96     {
 97         init();
 98         scanf("%d%d%d",&n,&m,&s);
 99         while(m--)
100         {
101             int u,v;
102             scanf("%d%d",&u,&v);
103             add(u,v);
104             add(v,u);
105         }
106         if(BFS(s)&&!Color(s))
107         {
108             printf("Case %d: YES
",++cas);
109         }
110         else
111         {
112             printf("Case %d: NO
",++cas);
113         }
114     }
115     return 0;
116 }

View Code