10004 - Bicoloring

32340

42.67%

8939

86.93%

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105

题目类型：搜索

题目：

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代码：

#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 LOCALfreopen("input.txt","r",stdin);
#endifwhile(~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代码：

#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;}}}
}int main(){
#ifdef LOCALfreopen("input.txt","r",stdin);
#endifwhile(~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;
}