Back to Category
p035: [Week 12] Bicoloring
Keyword: Miguel Revilla 2000-08-21

Difficulity: 2 | Test Data Sets: 5 (Hidden) | Judging: Traditional Judge
Accepted : 251 Times | Submit :941 Times | Clicks : 2832
Accepted : 149 Users | Submit : 163 Users | Accepted rate : 91%
Time Limit :1000 ms | Memory Limit : 64000 KBytes
Update : 2015-06-12 09:27

Content:

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:

 

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 (0 <= a < n).

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:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
3
3
0 1
1 2
2 0
0

Sample Output :

BICOLORABLE.
NOT BICOLORABLE.

Hint :

Author :

Miguel Revilla 2000-08-21 (Manager: taskmanager)

  Solve it!   Status Forum

C
C++
JAVA
PASCAL
20184. EEL
(0ms, 114KB, 397B)
5095. rainism
(0ms, 638KB, 377B)

Program running time may be affected by various factors. Check server system environment information here