ZeroJudge D768: Bicoloring

UVa 10004 – Bicoloring

The Four Color Map Theorem, proven with the help of computers in 1976, states that no more than four colors are required to color the regions of a map such that no two adjacent regions share the same color. This theorem applies to any planar map, ensuring that four colors are always sufficient to achieve this condition.

Now, you need to solve a similar but simpler problem. Given a connected graph, you are required to color the nodes using only two different colors and determine whether it is possible to color the nodes such that no two adjacent nodes have the same color. To simplify the problem, you can assume:

  • No node will have an edge connecting to itself.
  • Edges are undirected, meaning that if node A can connect to node B, then node B can also connect to node A.
  • The graph is strongly connected, meaning there is a path between any two nodes.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
EOF input: For each test case, the first line contains a positive integer N (1 < N < 200) representing the number of nodes. The second line contains a positive integer M, representing the number of edges. The following M lines contain two integers representing the nodes connected by an edge. The nodes are numbered from 0 to N-1. N = 0 indicates the end of the input.For each set of test data, output whether it is possible to color the nodes using 2 different colors such that adjacent nodes do not share the same color. If it is possible, output "BICOLORABLE." Otherwise, output "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 Sample Test Case

Thought Process

Use the BFS approach to determine if any node can return to itself with the same color. If this is the case, it means that adjacent nodes will have the same color.

Sample Code－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
Tags

Related Posts

Comments