UVA-10004 - Bicoloring

  • UVa Online Judge 解題結果請於 Submit 後,參閱 uHunt
  • 如果你有任何建議與指教,歡迎於下方留言一起討論喔!
  • 本題選為「20180327 大學程式能力檢定 CPE」題目。
  • 相同題目:ZOJ-d768

題意概要

本題為「四色地圖理論 (Four Color Map Theorem)」。簡單來說,就是僅以四種顏色在地圖上不同的區域塗色,使得相鄰的區域顏色均不相同。題目將給你一個相連的圖,請你在節點上塗色 (只有 種不同的顏色),並且回答是否可以使得相鄰的節點顏色均不相同。為了使問題簡單一些,你可以假設:


Input

The input consists of several test cases. Each test case starts with a line containing the number () of different nodes. The second line contains the number of edges . After this, 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 (). An input with 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

3
3
0 1
1 2
2 0
3
2
0 1
1 2
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0

Sample Output

NOT BICOLORABLE.
BICOLORABLE.
BICOLORABLE.
profile-image
Yung-Sheng Lu
Hello, I'm Yung-Sheng Lu. I am a graduate student in Department of Computer Science at National Chiao Tung University, Taiwan. I am in the Networking and Sensing Systems (NSS) Lab at NCTU.
comments powered by Disqus