k 部图判定

题面

正在打集的 Displace_ 瞅了一眼U群，发现大家在讨论 NPC 问题，看着集成战略的地图，他突然想到了一个经典 NPC 问题：图染色。

经典的图染色问题是一个 $n$ 个点 $m$ 条边的无向连通图，用 $k$ 种颜色来给每个点染色，使得任意有边连接的两个点颜色不同，构造一个方案。

$k=1$ 是简单的，当 $k=2$ 时问题的难度就骤增了，所以仁慈的 Displace_ 保证 $k\leq3$ 。

但即使是 $k=3$ 的问题，在边较多的图上也是及其棘手的，所以 Displace_ 保证图的边数不多，具体的，有一个阈值 $t$ ，保证 $m\leq n+t$ 。

被邪魔污染的 Displace_ 决定就限制这么多条件，现在你需要在这样的条件下构造出一个染色方案，或者报告无解。

$n\leq10^5$ .

题解

一开始写的是邓老师的调整法做法，只拿到 45pts。正解是随机化 + 2-SAT，见 OI-wiki。但是这个做法太邪神了，不好维护。记乱搞做法。

代码

constexpr static bool T = 0;
constexpr static int N = 100005, C = 100;
mt19937 rnd(0);
int c[N], s[N], t[N];
bool vis[N];
vector<int> e[N];
vector<pair<int, int>> ep;

void dfs(int x, int fa) {
    shuffle(e[x].begin(), e[x].end(), rnd);
    for (int i : e[x]) {
        if (i != fa) {
            if (!c[i]) {
                c[i] = 3 - c[x];
                dfs(i, x);
            } else if (c[i] == c[x])
                ep.emplace_back(i, x);
        }
    }
    return;
}

bool solve(int n) {
    ep.clear();
    s[0] = 0;
    for (int i = 1; i <= n; ++i) c[i] = 0;
    int x = rnd() % n + 1;
    c[x] = 1;
    dfs(x, 0);
    if (ep.empty())
        return 1;
    for (pair<int, int> p : ep) {
        s[++s[0]] = p.first;
        s[++s[0]] = p.second;
        t[p.first] = c[p.first];
        t[p.second] = c[p.second];
        vis[p.first] = 1;
        vis[p.second] = 1;
    }
    for (int i = 1; i <= s[0]; ++i)
        for (int k : e[s[i]])
            if (vis[k])
                ep.emplace_back(s[i], k);
    bool flg = 0;
    for (int i = 500; i && !flg; --i) {
        int x = rnd() % s[0] + 1, y = rnd() & 1;
        t[s[x]] = y ? 3 : c[s[x]];
        flg = 1;
        for (pair<int, int> p : ep)
            if (t[p.first] == t[p.second]) {
                flg = 0;
                break;
            }
    }
    if (flg)
        for (int i = 1; i <= s[0]; ++i) c[s[i]] = t[s[i]];
    for (int i = 1; i <= s[0]; ++i) vis[s[i]] = 0;
    return flg;
}

void solve() {
    read();
    int n = read(), m = read(), k = read(), t = read();
    bool flg;
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    if (k == 1) {
        if (m) {
            puts("-1");
            return;
        }
        puts("1");
        for (int i = 1; i <= n; ++i) printf("1 ");
        putchar('\n');
        return;
    }
    if (k == 2) {
        c[1] = 1;
        dfs(1, 0);
        if (ep.size()) {
            puts("-1");
            return;
        }
        puts("1");
        for (int i = 1; i <= n; ++i) printf("%d ", c[i]);
        putchar('\n');
        return;
    }
    for (int i = C; i && !(flg = solve(n));) --i;
    if (!flg) {
        puts("-1");
        return;
    }
    puts("1");
    for (int i = 1; i <= n; ++i) printf("%d ", c[i]);
    putchar('\n');
    return;
}