Note: This article is available in Chinese only. 本文暂无英文版本。
View original
思路：询问一个无向图，是否存在奇数环，以及是否存在偶数环。（不同的环之间可以有相同的点，不能有相同的边）
思路：一开始的想法是，根据染色的奇偶性，如果染色到某个之前染色过的点，和当前要染的颜色相同，说明存在奇数环，不同，说明存在偶数环。
感觉很有道理的做法，然而错了，发现是忽略了上面说的，不同的环之间由相同的点的情况。
比如这组数据：
5 6
1 2
2 3
3 1
1 4
4 5
5 1
两个三元环扣在一起。
实际上是既有奇数环，又有偶数环的。
但是按照我的做法，由于每次只去染没有染过的点，无法发现偶数环。
因此正解是增加一步回溯，这样使得之前存在与某个环中的点还可以出现在其他环中。
然而这样复杂度会炸。
于是我们根据每条边只能走一次，对边加一个 vis，使得每条边只走一次，从而保证复杂度。
好题！
这道题我看到了三种解法，第一种是官方解法，tarjan 什么（没仔细看）。
第二种是交叉染色。
但是我们可以发现，在这样的情况下，偶环是否和奇环是有联系的，即能不能根据两个奇环的关系，来判断偶环是否存在。
做法：判断是否存在一个点，同时属于两个奇环，如果存在，那么这两个奇环一定可以构成偶环。
证明：令两个奇环分别有 x1、x2 条边，如果两个环存在一个公共点，令它们存在 y 条公共边，则它们合并成的环有 x1+x2-2*y 条边，一定是偶环。因为题目中限制的是边的通过次数，所以即使像下面这组数据一样 y=0，偶环是交叉的，也是符合题意的。
但是代码略长，而且还要记录路径。
第三种做法就是我这里用到的做法，感觉很完美，可以当模板 23333。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年09月01日 星期四 14时47分32秒
4File Name :code/hdu/5215.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec secon
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=1E5+7;
32const int M=3E5+7;
33int n,m;
34int col[N];
35bool even,odd;
36bool vis[N];
37int cnt ;
38int head[N];
39struct Edge
40{
41 int v;
42 int nxt;
43 bool vis;
44}edge[2*M];
45void addedge( int u,int v)
46{
47 edge[cnt].v = v;
48 edge[cnt].nxt = head[u];
49 edge[cnt].vis = false;
50 head[u] = cnt;
51 cnt++;
52}
53void dfs( int u,int x,int fa)
54{
55 col[u] = x;
56 for ( int i = head[u] ; i !=-1 ; i = edge[i].nxt)
57 {
58 int v = edge[i].v;
59 if (v==fa) continue;交叉染色法判断无向图的奇偶环
60 if (col[v]!=-1)
61 {
62 if (col[v]==x) odd = true;
63 else even = true;
64 }
65 if (!edge[i].vis)
66 {
67 edge[i].vis = true;
68 dfs(v,1-x,u);
69 }
70 }
71 col[u] = -1;
72}
73void solve()
74{
75 odd = false;
76 even = false;
77 for ( int i = 1 ; i <= n ; i++){
78 if (col[i]==-1) dfs(i,0,-1);
79 }
80}
81int main()
82{
83 #ifndef ONLINE_JUDGE
84 freopen("code/in.txt","r",stdin);
85 #endif
86 int T;
87 cin>>T;
88 while (T--)
89 {
90 scanf("%d%d",&n,&m);
91 ms(col,-1);
92 ms(head,-1);
93 cnt = 0 ;
94 for ( int i = 1 ;i <= m ; i++)
95 {
96 int u,v;
97 scanf("%d%d",&u,&v);
98 addedge(u,v);
99 addedge(v,u);
100 }
101 solve();
102 if (odd) puts("YES");else puts("NO");
103 if (even) puts("YES");else puts("NO");
104 }
105 #ifndef ONLINE_JUDGE
106 fclose(stdin);
107 #endif
108 return 0;
109}