题解：P8076 [COCI2009-2010#7] RESTORAN

Pengzt · 2025-01-10 15:56:53 · 题解

RESTORAN

题目链接。cnblogs。

Problem

给定一张 n 个点，m 条边的无向图。现在要求一种对边的染色的方式，使得每个度数不小于 2 的点基于白色边相连，又与黑色边相连。无解输出 -1。

数据范围：1 \le n, m \le 10^5，不保证没有重边。

Sol

经典套路？先考虑无解的情况，当且仅当存在一个长为奇数且没有多余边的环时无解。

对于有解的情况，建虚点，连向所有奇度数的点。为了有解，随便从一个度数大于 2 的点开始跑欧拉回路，然后直接交替染色即可。由于环长为偶数或者有其它的边，所以一定有解。时间复杂度 \mathcal{O}(n + m)。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
mt19937_64 eng(time(0) ^ clock());
template <typename T>
T rnd(T l, T r) { return eng() % (r - l + 1) + l; }
int n, m, em;
vector<pii> e[100005];
int cnt, co, deg[100005], id[100005], col[200005], vse[200005], vsp[100005];
int cur[100005];
void DFS(int u) {
    vsp[u] = 1;
    for (int &i = cur[u]; i < (int) e[u].size(); ) {
        int v = e[u][i].fi, id = e[u][i].se;
        ++i;
        if (vse[id])
            continue;
        vse[id] = 1;
        ++cnt;
        DFS(v);
        col[id] = (co = 3 - co);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) id[i] = i;
    for (int i = 1, u, v; i <= m; i++)
        scanf("%d%d", &u, &v),
        e[u].emplace_back(v, i), e[v].emplace_back(u, i),
        deg[u]++, deg[v]++;
    sort(id + 1, id + n + 1, [&](int x, int y) { return deg[x] > deg[y]; });
    em = m;
    for (int i = 1; i <= n; i++)
        if (deg[i] & 1)
            em++, e[i].emplace_back(0, em), e[0].emplace_back(i, em);
    co = 1;
    DFS(0);
    for (int i = 1; i <= n; i++) {
        if (vsp[id[i]])
            continue;
        cnt = 0;
        DFS(id[i]);
        if (cnt % 2 == 1 && deg[id[i]] <= 2)
            return puts("0"), 0;
    }
    for (int i = 1; i <= m; i++)
        printf("%d\n", col[i]);
    return 0;
}