uva 10004 Bicoloring（并查集） Bicoloring

63 阅读 0 评论 42 点赞

我是靠谱客的博主认真小熊猫，最近开发中收集的这篇文章主要介绍uva 10004 Bicoloring（并查集） Bicoloring ，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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.

Input

The input consists of several test cases. Each test case starts with a line containing the number n ( 1 < n < 200) of different nodes. The second line contains the number of edges l . After this, l lines will follow, each containing two numbers that specify an edge between the two nodes that they represent. A node in the graph will be labeled using a number a (

An input with n = 0 will mark the end of the input and is not to be processed.

Output

You have to decide whether the input graph can be bicolored or not, and print it as shown below.

Sample Input

Sample Output

NOT BICOLORABLE.
BICOLORABLE.

题目大意：有N个点，给出m组数据，数据的两个值表示两个点相邻，用两种颜色填充，相邻的两个点不能拥有相同的颜色，判断是否成立。

解题思路：用并查集的知识，用一个结构体去表示一个点，结构体中一个记录与他相邻的点，一个记录它与相邻节点的关系，当出现有两个点的根是相同时，就分别判断他们与根的关系，如果相同就不满足。

#include<stdio.h>
#define N 205
struct rode{
int value;
int dis;
}num[N];
int n, t, bo;
int get_fa(int x, int &sum){
sum += num[x].dis;
return x != num[x].value?get_fa(num[x].value, sum):x;
}
int main(){
while (scanf("%d", &n), n){
// Init.
for (int i = 0; i < n; i++){
num[i].value = i;
num[i].dis = 0;
}
bo = 0;
// Read.
scanf("%d", &t);
for (int i = 0; i < t; i++){
int a, b, pi = 0, qi = 0;
scanf("%d%d", &a, &b);
int p = get_fa(a, pi), q = get_fa(b, qi);
if(p == q){
if (pi % 2 == qi % 2)
bo = 1;
}
else{
num[p].value = q;
if (pi % 2 != qi % 2)
num[p].dis = 0;
else
num[p].dis = 1;
}
}
if (bo)
printf("NOT BICOLORABLE.n");
else
printf("BICOLORABLE.n");
}
return 0;}