hdu 5215 Cycle(交叉染色法判断无向图的奇偶环)
思路:询问一个无向图，是否存在奇数环，以及是否存在偶数环。（不同的环之间可以由相同的点，不能有相同的边）
思路：一开始的想法是，根据染色的奇偶性，如果染色到某个之前染色过的点，和当前要染的颜色相同，说明存在奇数环，不同，说明存在偶数环。
感觉很有道理的做法。。。然而错了。。。发现是忽略了上面说的，不同的环之间由相同的点的情况。
比如这组数据：
5 61 2
2 3
3 1
1 4
4 5
5 1
两个三元环扣在一起。
实际上是既有奇数环，又有偶数环的。
但是按照我的做法，由于每次只去染没有染过的点，无法发现偶数环。
因此正解是增加一步回溯，这样使得之前存在与某个环中的点还可以出现在其他环中。
然而这样复杂度会炸。。。
于是我们根据，每条边只能走一次，对边加一个vis，使得每条边只走一次，从而保证复杂度。
好题！
这道题我看到了三种解法，第一种是官方解法，tarjan什么（没仔细看）。
第二种是交叉染色。
但是我们可以发现，在这样的情况下，偶环是否和奇环是有联系的，即能不能根据两个奇环的关系，来判断偶环是否存在。做法：判断是否存在一个点，同时属于两个奇环，如果存在，那么这两个奇环一定可以构成偶环。
证明：令两个奇环分别有x1、x2条边，如果两个环存在一个公共点，令他们存在y条公共边，则它们合并成的环有x1+x2-2*y条边，一定是偶环。因为题目中限制的是边的通过次数，所以即使像下面这组数据一样y=0，偶环是交叉的，也是符合题意的。
但是代码略长，而且还要记录路径。
第三种做法就是我这里用到的做法。。。感觉很完美。。可以当模板23333
/* ***********************************************
Author :111qqz
Created Time :2016年09月01日 星期四 14时47分32秒
File Name :code/hdu/5215.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec secon
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
const int M=3E5+7;
int n,m;
int col[N];
bool even,odd;
bool vis[N];
int cnt ;
int head[N];
struct Edge
{
int v;
int nxt;
bool vis;
}edge[2*M];
void addedge( int u,int v)
{
edge[cnt].v = v;
edge[cnt].nxt = head[u];
edge[cnt].vis = false;
head[u] = cnt;
cnt++;
}
void dfs( int u,int x,int fa)
{
col[u] = x;
for ( int i = head[u] ; i !=-1 ; i = edge[i].nxt)
{
int v = edge[i].v;
if (v==fa) continue;交叉染色法判断无向图的奇偶环
if (col[v]!=-1)
{
if (col[v]==x) odd = true;
else even = true;
}
if (!edge[i].vis)
{
edge[i].vis = true;
dfs(v,1-x,u);
}
}
col[u] = -1;
}
void solve()
{
odd = false;
even = false;
for ( int i = 1 ; i <= n ; i++){
if (col[i]==-1) dfs(i,0,-1);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
int T;
cin>>T;
while (T--)
{
scanf("%d%d",&n,&m);
ms(col,-1);
ms(head,-1);
cnt = 0 ;
for ( int i = 1 ;i <= m ; i++)
{
int u,v;
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
solve();
if (odd) puts("YES");else puts("NO");
if (even) puts("YES");else puts("NO");
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}