HDU
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 ",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 = 200907; int T; void testcase(){ printf("Case %d: ",++T); } const int MAXN = 1e6+5; const int MAXM = 30; struct node{ int v,nxt; }e[MAXN*2]; int head[2*MAXN],deg[MAXN],color[MAXN],n,m,cnt; void init(){ mset(head,-1); mset(deg,0); mset(color,0); cnt=0; } void addEdge(int u,int v){ e[cnt].v=v; e[cnt].nxt=head[u]; head[u]=cnt++; } int bfs(int rt){ color[rt]=1; 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 1; if(!color[v]){ color[v]=-color[u]; que.push(v); } } } return 0; } int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL int t,s,u,v; scd(t); T=0; while(t--){ scddd(n,m,s); init(); for(int i=0;i<m;i++){ scdd(u,v); addEdge(u,v); addEdge(v,u); deg[u]++,deg[v]++; } int f=0; for(int i=0;i<n;i++){ if(!deg[i]){ f=1; break; } } testcase(); if(f){ puts("NO"); continue; } if(bfs(0)) puts("YES"); else puts("NO"); } return 0; }