題目：
In 1976 the ``Four Color Map Theorem" was proven with the assistance of a computer. This theorem states that every map can be colored using only four colors, in such a way that no region is colored using the same color as a neighbor region.
Here you are asked to solve a simpler similar problem. You have to decide whether a given arbitrary connected graph can be bicolored. That is, if one can assign colors (from a palette of two) to the nodes in such a way that no two adjacent nodes have the same color. To simplify the problem you can assume:
no node will have an edge to itself.
the graph is nondirected. That is, if a node a is said to be connected to a node b, then you must assume that b is connected to a.
the graph will be strongly connected. That is, there will be at least one path from any node to any other node.
題目翻譯：
1976年“四色定理”在計算機的幫助下被證明。 這個定理宣告任何一個地圖都可以只用四種顏色來填充， 並且沒有相鄰區域的顏色是相同的。
現在讓你解決一個更加簡單的問題。 你必須決定給定的任意相連的圖能不能夠用兩種顏色填充。 就是說，如果給其中一個分配一種顏色， 要讓所有直接相連的兩個節點不能是相同的顏色。 為了讓問題更簡單，你可以假設：
1. 沒有節點是連接向它自己的。
2. 是無向圖。 即如果a連接b, 那麼b也是連接a的
3. 圖是強連接的。就是說至少有一條路徑可走向所有節點。
樣例輸入：
3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0
樣例輸出：
NOT BICOLORABLE.
BICOLORABLE.
分析與總結：
方法一：廣搜ＢＦＳ
由題目可知，對於每個結點，所有和它相接的點必須和這個點顏色不一樣。那麼，很自然可以用廣搜來做： 選取其中一點，給這個點賦值為一種顏色，可以用數字0來代替，然後進行廣搜，那麼所有和他相鄰的點就可以賦值為另一種顏色，可以用1來代替。如此搜下去， 如果遇到一個點是已經賦值過了的，那就進行判斷，他已經有的值是不是和這次要給它的值相同的，如果是相同的，就繼續。如果不同的話，那麼直接判斷為不可以。
BFS代碼：
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 210
using namespace std;
int n, m, a, b, G[MAXN][MAXN], lastPos;
int vis[210],edge[250][2];
bool flag;
int que[100000];
void bfs(int pos){
int front=0, rear=1;
que[0] = pos;
while(front < rear){
int m = que[front++];
for(int i=0; i<n; ++i){
if(G[m][i]){
if(!vis[i]){
que[rear++] = i;
vis[i] = vis[m]+1;
}
else if(vis[i]==vis[m]){
flag = true;
return;
}
}
}
}
}
int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif
while(~scanf("%d",&n) && n){
memset(G, 0,sizeof(G));
scanf("%d",&m);
for(int i=0; i<m; ++i){
scanf("%d %d",&a,&b);
G[a][b] = 1;
G[b][a] = 1;
}
memset(vis, 0, sizeof(vis));
vis[0] = 1;
flag = false;
bfs(0);
if(flag) printf("NOT BICOLORABLE.\n");
else printf("BICOLORABLE.\n");
}
return 0;
}
方法二： 深搜DFS
同樣，這題也可以用深搜來做。 深搜的基本思想是，沿著一個方向不斷搜下去，沒走一步都進行染色，當前這一點的色和上一點的色相反。如果搜到了一個染過的（即有回環），那麼也進行判斷，已經有的色是不是和這次給它的顏色是否一致的。不一致的話，就判斷為不可以。
DFS代碼：
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 210
using namespace std;
int n, m, a, b, G[MAXN][MAXN], lastPos;
int vis[210];
bool flag;
void dfs(int pos){
if(flag) return;
for(int i=0; i<n; ++i){
if(G[pos][i]){
if(vis[i]==-1){
vis[i] = !vis[pos];
dfs(i);
vis[i] = -1;
}
else if(vis[i] != !vis[pos]){
flag = true;
return;
}
}
} www.2cto.com
}
int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif
while(~scanf("%d",&n) && n){
memset(G, 0,sizeof(G));
scanf("%d",&m);
for(int i=0; i<m; ++i){
scanf("%d %d",&a,&b);
G[a][b] = 1;
G[b][a] = 1;
}
flag = false;
memset(vis, -1, sizeof(vis));
vis[0] = 0;
dfs(0);
if(flag) printf("NOT BICOLORABLE.\n");
else printf("BICOLORABLE.\n");
}
return 0;
}
