题目链接:
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.
分析与总结:
以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索颜色
, node
, 节点
, 题目
, Connected
The
uva oj、uva和uvb的区别、uvb、uva大学、弗吉尼亚大学,以便于您获取更多的相关知识。