UVa 10004：Bicoloring

UVa 10004：Bicoloring2014-10-11 csdn博客 shuangde800题目链接：

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. 图是强连接的。就是说至少有一条路径可走向所有节点。

样例输入：

330 11 22 0980 10 20 30 40 50 60 70 80

样例输出：

NOT BICOLORABLE.BICOLORABLE.

分析与总结：