ZeroJudge D768: Bicoloring

同題：UVa 10004 – Bicoloring

1976 年，在電腦協助之下證明了 4 色地圖理論 (Four Color Map Theorem）。就是僅以 4 種顏色在地圖上不同的區域塗色，使得相鄰的區域顏色均不相同。

現在，你要解決一個類似，但比較簡單的問題。給你一個相連的圖，請你在節點上塗色 (只有 2 種不同的顏色），並且回答是否可以使得相鄰的節點顏色均不相同。為了使問題簡單一些，你可以假設：

  • 沒有節點會有連向自己的邊。
  • 邊是沒有方向性的，也就是說如果節點 A 可以連到節點 B，那麼代表節點 B 也可以連到節點 A。
  • 圖形是強連通的，也就是說任 2 節點之間皆有路徑相連。

範例測資

範例輸入範例輸出
EOF 輸入，每組測試資料的第一列有一個正整數 N (1 < N < 200) 代表節點的數目。第二列有一個正整數 M，代表邊的數目。接下來的 M 列每列有 2 個整數代表邊所連接的 2 個節點的代號。這 N 個節點的代號分別為 0 到 N-1。
N = 0 代表輸入結束。		對每一組測試資料輸出是否可以用 2 種顏色塗節點使得相鄰的節點顏色均不相同。若可以請輸出：「BICOLORABLE.」，否則輸出：「NOT BICOLORABLE.」。
3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0		NOT BICOLORABLE.
BICOLORABLE.
ZeroJudge D768 範例測資

解題思路

使用 BFS 的方式去判斷每一個點是否可以走回自己且顏色一樣，如果是的話就代表相鄰的節點顏色會有相同的情況。

範例程式碼－ZeroJudge D768: Bicoloring

#include <iostream>
#include <map>
#include <vector>
using namespace std;

map<int, vector<int>>MAP;
map<int, int>walk;
int N;

int change(int c) {
    if (c == 1) c = 2;
    else c = 1;
    return c;
}

bool BFS(const vector<int>start, const int target , int color) {
    if (start.size() == 0) return true;
    vector<int>newStart;
    map<int, int>push;
    for (int i = 0; i<start.size(); i++) {
        if (walk[start[i]] == color) return false;
        walk[start[i]] = color;
        for (int j = 0; j<MAP[start[i]].size(); j++) {
            const int num = MAP[start[i]][j];
            if (walk[num] == 0 && push[num] == 0) {
                push[num]++;
                newStart.push_back(num);
            }
        }
    }
    change(color);
    return BFS(newStart, target , color);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    while (cin >> N && N != 0) {
        MAP.clear();
        walk.clear();
        int M;
        cin >> M;
        for (int i = 0; i<M; i++) {
            int a, b;
            cin >> a >> b;
            MAP[a].push_back(b);
            MAP[b].push_back(a);
        }
        bool ok = true;
        for (int i = 0; i<N; i++) {
            if (walk[i] > 0) continue;
            vector<int>start;
            start.push_back(i);
            if (!BFS(start, i , 1)) {
                cout << "NOT BICOLORABLE.\n";
                ok = false;
                break;
            }
        }
        if (ok) cout << "BICOLORABLE.\n";
    }
}

//ZeroJudge D768
//Dr. SeanXD
標籤

相關文章

發佈留言