UVA10004 Bicoloring 题解

SunnyYuan · 2023-09-05 20:23:11 · 题解

随机跳到的。

思路

这个是一个二分图的判定的模板题。

主要思路就是判断图中是否有奇环。

我们主要是对图进行染色。

相邻的两个点采取不同的颜色。

像这样：

如果染色染到中途发现点 u 和 点 v 之间右边相连且颜色相同，说明出现矛盾（就可以返回并输出 NOT BICOLORABLE.）。

如果到最后都没有遇到错误，那么输出 BICOLORABLE.。

代码

/*******************************
| Author:  SunnyYuan
| Problem: In 1976 the \Four Color Map Theorem " was proven with the assistance of a computer. This theorem - states that every map can be colored using only four colors, in such a way that no region is colored
| Contest: UVa Online Judge
| URL:     https://onlinejudge.org/external/100/p10004.pdf
| When:    2023-09-06 15:41:13
| 
| Memory:  1024 MB
| Time:    1000 ms
*******************************/

#include <bits/stdc++.h>

using namespace std;

const int N = 210;

int n, m;
vector<int> e[N];
int color[N];

bool dfs(int u, int col) {
    color[u] = col;
    for (int to : e[u]) {
        if (!color[to]) {
            if (!dfs(to, 3 - col)) return false;
        }
        else {
            if (color[to] == color[u]) return false;
        }
    }
    return true;
}

void solve() {
    for (int i = 0; i < n; i++) {
        color[i] = 0;
        e[i].clear();
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    for (int i = 0; i < n; i++) {
        if (!color[i]) {
            if (!dfs(i, 1)) {
                cout << "NOT BICOLORABLE.\n";
                return;
            }
        }
    }

    cout << "BICOLORABLE.\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while (cin >> n >> m, n) solve();
    return 0;
}