UVa 10004 - Bicoloring

题目：
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.zzzyk.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){
            s

补充：软件开发 , C++ ,