题意
小偷在跑路，如果他t时刻在u街区，那么他在t+1时刻出现在v街区的条件是，u和v街区之间有一个街区把两个街区隔开。
问，是否有某一个时刻小偷可能出现在所有城市。
思路
如果小偷有某一个时刻可能出现在所有城市，首先我们一定要确保整个图是连通的，如果整个图不是连通的，则肯定有城市小偷无法抵达。可以用并查集 判断图是否连通。 但是本题输入保证图连通，故不需要再判。
如果说u，v街区之间正好有一个街区把两个街区分开，很像涂色问题中的相邻的节点涂不同颜色。如果是二分图 ，不妙，小偷要么出现在黑色区域，要么出现在白色区域，不会有某一时刻有出现在所有城市的可能性。
所以直接判断图是否为二分图即可
如果是二分图则NO， 不是二分图YES
记录
在做这道水题的时候为了少打点字儿省事用了cin, cout超时了, 偶然间发现了这样一个骚操作 ：
参考 ： 关于ios::sync_with_stdio(false);和 cin.tie(0)加速c++输入输出流
ios::sync_with_stdio(false);
cin.tie(0);cin，cout之所以效率低，是因为先把要输出的东西存入缓冲区，再输出，导致效率降低，第1句可以来打消iostream的输入 输出缓存，可以节省许多时间，使效率与scanf与printf相差无几.
tie是将两个stream绑定的函数，空参数的话返回当前的输出流指针。
sync_with_stdio这个函数是一个“是否兼容stdio”的开关，C++为了兼容C，保证程序在使用了std::printf和std::cout的时候不发生混乱，将输出流绑到了一起。
在ACM里，经常出现 数据集超大造成 cin TLE的情况。这时候大部分人（包括原来我也是）认为这是cin的效率不及scanf的错，甚至还上升到C语言和C++语言的执行效率层面的无聊争论。其 实像上文所说，这只是C++为了兼容而采取的保守措施。我们可以在IO之前将stdio解除绑定，这样做了之后要注意不要同时混用cout和printf 之类。
在默认的情况下cin绑定的是cout，每次执行 << 操作符的时候都要调用flush，这样会增加IO负担。可以通过tie(0)（0表示NULL）来解除cin与cout的绑定，进一步加快执行效率。
如下所示：
#include <iostream>
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
// IO
}AC代码
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#define mst(a) memset(a, 0, sizeof(a));
using namespace std;
const int maxn = 100000+5;
vector<int> g[maxn]; //图
int clr[maxn]; //记录颜色为1/-1
int n, m, s;
bool dfs(int v, int c){
clr[v] = c;
for( int i = 0; i < g[v].size(); i++ ){
if( clr[g[v][i]] == c ) return false; //如果联通的已经有涂成c色的了
if( clr[g[v][i]] == 0 && !dfs(g[v][i], -c) ) return false;
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T, a, b;
cin >> T;
for( int t = 1; t <= T; t++ ){
//mst(f);
cin >> n >> m >> s;
mst(clr);
for( int i = 0; i < n; i++ )
if(g[i].size())
g[i].clear();
for( int i = 0; i < m; i++ ){
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
cout << "Case "<< t << ": ";
if(!dfs(s,1)) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}