题目翻译：
1976年“四色定理”在计算机的帮助下被证明。 这个定理宣告任何一个地图都可以只用四种颜色来填充， 并且没有相邻区域的颜色是相同的。
现在让你解决一个更加简单的问题。 你必须决定给定的任意相连的图能不能够用两种颜色填充。 就是说，如果给其中一个分配一种颜色， 要让所有直接相连的两个节点不能是相同的颜色。 为了让问题更简单，你可以假设：
1. 没有节点是连接向它自己的。
2. 是无向图。 即如果a连接b, 那么b也是连接a的
3. 图是强连接的。就是说至少有一条路径可走向所有节点。
方法一：广搜ＢＦＳ
由题目可知，对于每个结点，所有和它相接的点必须和这个点颜色不一样。那么，很自然可以用广搜来做： 选取其中一点，给这个点赋值为一种颜色，可以用数字0来代替，然后进行广搜，那么所有和他相邻的点就可以赋值为另一种颜色，可以用1来代替。如此搜下去， 如果遇到一个点是已经赋值过了的，那就进行判断，他已经有的值是不是和这次要给它的值相同的，如果是相同的，就继续。如果不同的话，那么直接判断为不可以。
方法二： 深搜DFS
同样，这题也可以用深搜来做。 深搜的基本思想是，沿着一个方向不断搜下去，没走一步都进行染色，当前这一点的色和上一点的色相反。如果搜到了一个染过的（即有回环），那么也进行判断，已经有的色是不是和这次给它的颜色是否一致的。不一致的话，就判断为不可以。
//bfs
#include <stdio.h> #include <string.h> #include <queue> #define N 220 using namespace std; queue <int> q; bool g[N][N]; int vis[N]; int n,m; int main() { int i,j,u,v,ok; int tmp,colour; while(scanf("%d",&n)!=EOF && n) { scanf("%d",&m); memset(g,0,sizeof(g)); memset(vis,0,sizeof(vis)); while(!q.empty()) q.pop(); for(i=1; i<=m; i++) { scanf("%d%d",&u,&v); g[u][v]=g[v][u]=1; } vis[0]=1; q.push(0); while(!q.empty()) { ok=1; tmp=q.front(); colour=vis[tmp]; for(i=0; i<n; i++) if(g[tmp][i]) { if(!vis[i]) { vis[i]=-colour; q.push(i); } else if( vis[i]!= (-colour)) { ok=0; break; } } if(!ok) break; q.pop(); } if(q.empty()) printf("BICOLORABLE.\n"); else printf("NOT BICOLORABLE.\n"); } return 0; }
//dfs #include <stdio.h> #include <string.h> #define N 220 bool g[N][N]; int vis[N]; int n,m; bool dfs(int s ,int colour) { int i; vis[s]=colour; for(i=0; i<n; i++) if(g[s][i]) { if(!vis[i]) { if(!dfs(i,-colour)) return 0; } else if( vis[i]!= (-colour) ) return 0; } return 1; } int main() { int i,u,v; while(scanf("%d",&n)!=EOF && n) { scanf("%d",&m); memset(g,0,sizeof(g)); memset(vis,0,sizeof(vis)); for(i=0; i<m; i++) { scanf("%d%d",&u,&v); g[u][v]=g[v][u]=1; } for(i=0; i<n; i++) if(!vis[i]) if(!dfs(i,1)) break; if(i<n) printf("NOT BICOLORABLE.\n"); else printf("BICOLORABLE.\n"); } }