本文共 2144 字,大约阅读时间需要 7 分钟。
32340 | 42.67% | 8939 | 86.93% |
题目类型:搜索
题目:
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:
题目翻译:
1976年“四色定理”在计算机的帮助下被证明。 这个定理宣告任何一个地图都可以只用四种颜色来填充, 并且没有相邻区域的颜色是相同的。
现在让你解决一个更加简单的问题。 你必须决定给定的任意相连的图能不能够用两种颜色填充。 就是说,如果给其中一个分配一种颜色, 要让所有直接相连的两个节点不能是相同的颜色。 为了让问题更简单,你可以假设:
1. 没有节点是连接向它自己的。
2. 是无向图。 即如果a连接b, 那么b也是连接a的
3. 图是强连接的。就是说至少有一条路径可走向所有节点。
样例输入:
330 11 22 0980 10 20 30 40 50 60 70 80
样例输出:
NOT BICOLORABLE.BICOLORABLE.
分析与总结:
方法一:广搜BFS
由题目可知,对于每个结点,所有和它相接的点必须和这个点颜色不一样。那么,很自然可以用广搜来做: 选取其中一点,给这个点赋值为一种颜色,可以用数字0来代替,然后进行广搜,那么所有和他相邻的点就可以赋值为另一种颜色,可以用1来代替。如此搜下去, 如果遇到一个点是已经赋值过了的,那就进行判断,他已经有的值是不是和这次要给它的值相同的,如果是相同的,就继续。如果不同的话,那么直接判断为不可以。
BFS代码:
#include#include #include #define MAXN 210using 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
方法二: 深搜DFS
同样,这题也可以用深搜来做。 深搜的基本思想是,沿着一个方向不断搜下去,没走一步都进行染色,当前这一点的色和上一点的色相反。如果搜到了一个染过的(即有回环),那么也进行判断,已经有的色是不是和这次给它的颜色是否一致的。不一致的话,就判断为不可以。
DFS代码:
#include#include #include #define MAXN 210using 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
转载地址:http://cyzni.baihongyu.com/