# UVA 10004 - Bicoloring

### 題意:
1976 年，著名的「四色地圖定理」在電腦協助下被證明。
該定理指出：任何地圖都能用四種顏色來上色，使得沒有相鄰地區使用相同的顏色。

目標:
判斷給定的任意連通圖是否可以雙色著色（bicolored）。
也就是，能否只用兩種顏色為圖中的節點上色，讓每對相鄰的節點都使用不同的顏色？

=> 判斷該圖能否讓==每對相鄰節點皆為不同顏色==。

你可以假設每張圖皆符合下列三點:
1. 沒有節點會與自己相連。
2. 為==無向圖==。
3. 為==連通圖==。(任意兩個節點之間，至少存在一條路徑可以連接)

### Sample Input:

輸入包含多筆測資。
每筆測資格式如下：
1. 第一行是一個整數 n，表示節點數量（1 < n < 200）。
2. 第二行是一個整數 l，表示邊的數量。
3. 接下來有 l 行，每行有兩個整數 a 和 b，代表節點 a 和節點 b 之間有一條邊。

節點編號為 0 到 n-1。
如果讀到 n = 0，表示輸入結束，這一行不需處理。

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:
如果這張圖可以雙色著色，輸出 "BICOLORABLE."
否則輸出 "NOT BICOLORABLE."

NOT BICOLORABLE.
BICOLORABLE.
BICOLORABLE.

### 程式碼:

**我的解法:**
如果沒有 cycle 的話，就是 bicolorable 的圖
如果有 cycle 的話，需要檢查 (去跑跑看DFS)

**小 tips:**
記得離散數學的話，判斷 cycle 的方式就很簡單了。
if 邊的數量 = 節點數量-1
就表示沒有 cycle，
大於等於表示有 cycle。
(這裡要注意: 是因為題目寫沒有自迴圈 + 為連通圖，再加上輸入的邊不會重複，才可以這樣解哦!)

btw. 就算沒判斷有沒有 cycle，直接全部丟 DFS 也會過。

#include <bits/stdc++.h>
using namespace std;

struct Node {
	int color;
	vector<int> nbs;
	Node() : color(0), nbs() {}
};

bool DFS(map<int, Node>& g, int i, int nowc) {
	g[i].color = nowc;
	if (nowc == 1) nowc = 2;
	else nowc = 1;

	for (auto& nb : g[i].nbs) {
		if (g[nb].color == 0) {
			if (!DFS(g, nb, nowc)) return false;
		}
		else if (g[nb].color == g[i].color) return false;
	}
	return true;
}

int main() {
	int n, e, t1, t2;
	while (cin >> n && n) {
		cin >> e;
		map<int, Node> g;
		for (int i = 0; i < e; i++) {
			cin >> t1 >> t2;
			g[t1].nbs.push_back(t2);
			g[t2].nbs.push_back(t1);
		}
		if (e == n - 1) {    // 這段沒有也可以過
			cout << "BICOLORABLE." << endl;
			continue;
		}
		if (DFS(g, 0, 1)) cout << "BICOLORABLE." << endl;
		else cout << "NOT BICOLORABLE." << endl;
	}
}