此筆記為UVa 10004的題目詳解，包含解題思路、C++範例程式碼。

Bicoloring (ZeroJudge d768.)

題目

1976 年，在電腦協助之下證明了 4 色地圖理論 (Four Color Map Theorem)。就是僅以 4 種顏色在地圖上不同的區域塗色，使得相鄰的區域顏色均不相同。 現在，你要解決一個類似，但比較簡單的問題。給你一個相連的圖，請你在節點上塗色 (只有2種不同的顏色)，並且回答是否可以使得相鄰的節點顏色均不相同。為了使問題簡單一些，你可以假設： • 沒有節點會有連向自己的邊。 • 邊是沒有方向性的，也就是說如果節點 A 可以連到節點 B，那麼代表節點 B 也可以連到節點 A。 • 圖形是強連通的，也就是說任 2 節點之間皆有路徑相連。

輸入 / 輸出說明

輸入說明 輸出說明
輸入含有多組測試資料。每組測試資料的第一列有一個正整數 𝑛 (1 < 𝑛 < 200) 代表節點的數目。第二列有一個正整數 𝑚，代表邊的數目。接下來的 𝑚 列每列有 2 個整數代表邊所連接的 2 個節點的代號。這 𝑛 個節點的代號分別為 0 到 𝑛-1。
𝑛 = 0 代表輸入結束。		 對每一組測試資料輸出是否可以用 2 種顏色塗節點使得相鄰的節點顏色均不相同。若可以請輸出：BICOLORABLE.，否則輸出：NOT BICOLORABLE.

解題思路

這類型題目他並沒有按照節點連結的關係給輸入資料，所以大家要注意一定要先建圖再走訪。 首先我用一個 vector relation[200] 存節點之間的關聯，relation[i] 代表是第 i 個點會連到的所有節點形成的 vector。 這樣我要去找有連接的地方就只需要找 relation[i] 內所有的元素即可。 接著我用 1、-1 當兩種顏色去塗節點 graph[i]，一開始先定義第 0 個點 (graph[0]) 為 1，接著就跑 DFS。 DFS 流程如下： 1. for 迴圈找所有有連接的節點 relation[node][i] 2. 判斷是否塗色 (1) 有塗色 => 如果是同色就直接 return 0 (絕對是 NOT BICOLORABLE) (2) 未塗色 => 進入 3. 3. 將連接的節點塗成這個節點的相反色 (graph[relation[node][i]] = graph[node] * (-1)) 4. 繼續從新的節點 relation[node][i] 開始跑 DFS 如果回傳是 0 就直接 return 0 (絕對是 NOT BICOLORABLE)

範例程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

int graph[200];

int dfs(int node, vector<int> relation[200])
{
	int i;
	
	for (i=0;i<relation[node].size();i++) {
		if (graph[relation[node][i]] == 0) {  // 未塗色 
			graph[relation[node][i]] = graph[node] * (-1);  // 塗相反色 
			
			if (dfs(relation[node][i], relation) == 0)
				return 0;
		}
		else {  // 有塗色 
			if (graph[relation[node][i]] == graph[node])  // 同色
				return 0;
		}
	}
	
	return 1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i;
	int n, l, a, b;
	
	while (cin >> n && n != 0) {
		cin >> l;
		
		vector<int> relation[200];
		
		for (i=0;i<200;i++)
			graph[i] = 0;
		
		for (i=0;i<l;i++) {
			cin >> a >> b;
			
			relation[a].push_back(b);
			relation[b].push_back(a); 
		}
		
		graph[0] = 1;  // 0 先塗一種顏色 
	
		if (dfs(0, relation) == 0)
			cout << "NOT BICOLORABLE." << '\n';
		else
			cout << "BICOLORABLE." << '\n';
	}
	
	return 0;
}

運行結果

AC (20ms, 592KB)

查看更多資訊請至：https://www.tseng-school.com/