uva 10004 Bicoloring （交叉染色法判断二分图模板题）
题意：给出一个无向图，问是否可以组成二分图。
思路：交叉染色法。
**首先任意取出一个顶点进行染色,和该节点相邻的点有三种情况:**** 1.未染色 那么继续染色此节点(染色为另一种颜色)**
** 2.已染色但和当前节点颜色不同 跳过该点**
** 3.已染色并且和当前节点颜色相同 返回失败(该图不是二分图)**
upd:更正dfs中的一个错误。
把dfs(v,1-x)改成了 if (!dfs(v,1-x)) return false;
之前的写法中，当前层之后的层的没有起到任何作用。。。
而实际上应该是后面只要某一层不满足，整体就该为false.
写成这样这题还能过我也是醉了。。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月31日 星期三 21时50分16秒
4File Name :code/uva/10004.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 second
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=205;
32vector <int>edge[N];
33int n,m;
34int col[N];
35bool dfs( int u,int x)
36{
37 col[u] = x;
38 int siz = edge[u].size();
39 for ( int i = 0 ; i < siz ; i++)
40 {
41 int v = edge[u][i];
42 if (col[v]==1-x) continue;
43 if (col[v]==x) return false;
44 if (!dfs(v,1-x)) return false;
45 }
46 return true;
47}
48int main()
49{
50 #ifndef ONLINE_JUDGE
51 freopen("code/in.txt","r",stdin);
52 #endif
53 while (~scanf("%d",&n))
54 {
55 if (n==0) break;
56 ms(col,-1);
57 for ( int i = 0 ;i <= n ; i++) edge[i].clear();
58 scanf("%d",&m);
59 for ( int i = 1 ; i <= m ; i++)
60 {
61 int u,v;
62 scanf("%d%d",&u,&v);
63 edge[u].push_back(v);
64 edge[v].push_back(u);
65 }
66 if (dfs(0,0))
67 puts("BICOLORABLE.");
68 else puts("NOT BICOLORABLE.");
69 }
70 #ifndef ONLINE_JUDGE
71 fclose(stdin);
72 #endif
73 return 0;
74}