题解：P14606 [NWRRC 2025] Games of Chess

Build_Dreams · 2026-07-23 14:43:59 · 题解

脑子被吃了，题目读错一个小时。参考了 Priestess_SLG 的题解。

我们将问题转化为每一个颜色导出的图对应的每个点度数都是奇数。

对于 2 \nmid n 的时候，显然无解。

:::info[证明] 每个点的度数都是奇数，那么总度数也为奇数，然而在任意一个子图中，度数之和应为偶数，度数之和为偶数，矛盾。 :::

接下来我们猜测 2 \mid n 的时候都有解。

尝试构造他，我们先尝试树，树我们可以对于每个叶子，如果父节点有偶数个儿子，那么将所有兄弟节点（包括自己）删掉并和父亲标记为同一种颜色，保留父亲，因为父亲现在连了偶数条边，还需连接奇数条边（这是原问题的子问题，于是直接保留父节点让父节点的父节点进行操作即可）否则如果父节点有奇数个儿子，直接将所有兄弟节点和父节点标记为同一种颜色并一道删除，因为它们的度数都已经符合条件了。

那么尝试推广，我们考虑 DFS 序。这个东西有“返祖边”的存在。

我们按照树的思路做，但是我们不好找“叶子”，换言之，我们不好动态维护叶子节点是哪些。

那么我们发现，\max dep 对应的节点一定是一个叶子，于是我们从深到浅操作每一个节点。

对于当前节点，还是从父亲节点入手。

如果父亲节点拥有奇数个儿子，那么这些节点和父节点直接一道删除并标记颜色即可。

否则，若拥有偶数个儿子，我们看看和之前的有什么不同。

注意到如果偶数个儿子有返祖边，我们设是 v \leftrightarrow nf，我们如果想以前一样保留父亲节点而标记所有兄弟节点的话，父亲节点可能会标记成和 nf 颜色一样。

那么处理起来也很简单，我们将这个单独处理的话，剩下的兄弟节点数量就是奇数了，我们直接将这奇数个节点做常规处理，并将 v 的父亲节点设为 nf，重新将新的 dep_v 对应的 v 加入队列中（这启示我们，当队列中取出的队头被对应的 dep 和现在当前节点的 dep 不同的时候，这个节点是以前的冗余节点，应跳过）。

否则没有返祖边，那就是常规处理即可。

代码很好写，但是也有细节。

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
bool begin_mem;
const int N = 2e5 + 5, M = 1e6 + 5;
const int inf = 1e9, mod = 998244353;
const ll INF = 1e18;

int n, m, fa[N], dep[N];
vector <int> g[N];
vector <int> tr[N];
vector <int> anc[N];
bool del[N], hav[N];
int poi[N];

void dfs(int f, int u){
    dep[u] = dep[f] + 1, fa[u] = f;
    for (auto v : g[u]){
        if (v == f) continue;
        if (!dep[v]) dfs(u, v), tr[u].push_back(v);
        else if (dep[v] < dep[u]) anc[u].push_back(v), hav[u] = 1;
    }
}

int p[N];
int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void merge(int u, int v){
    int pu = find(u), pv = find(v);
    if (pu == pv) return ;
    p[pu] = pv;
}

void init(){
}
void solve(){
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ ){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if (n & 1) cout << "-1\n";
    else{
        dfs(0, 1);

        priority_queue <pii> q;
        for (int i = 1; i <= n; i ++ ) q.push((pii){dep[i], i}), p[i] = i;
        for (int i = 1; i <= n; i ++ ) sort(anc[i].begin(), anc[i].end(), [&](int a, int b){
            return dep[a] > dep[b];
        });

        while (q.size()){
            auto [d, u] = q.top(); q.pop();
            if (del[u] || dep[u] != d) continue;
            int f = fa[u], hanc = -1;
            if (!f) continue;

            int tog = 0;
            for (auto v : tr[f]){
                if (del[v]) continue;
                tog ++, hanc = (hav[v] ? v : hanc);
            }
            if (tog & 1){
                for (auto v : tr[f]){
                    if (del[v]) continue;
                    del[v] = 1, merge(f, v);
                }
                del[f] = 1, merge(f, f);
            }
            else if (hanc == -1){
                // 考虑这个情况和树一样
                // 那么我们，把子树弄好然后这是偶数个挂给 f 了，那么我们其实可以直接删掉这些点
                // 那么 f 处理完，正好所有数字都是合理的了
                for (auto v : tr[f]){
                    if (del[v]) continue;
                    del[v] = 1, merge(f, v);
                }
            }
            else{
                // 这个时候就是说，我们的 hanc 这个节点要不被删，那么 hanc -> anc[hanc]
                //int nf = anc[hanc].back(); anc[hanc].pop_back();
                //int nf = anc[hanc].back(); anc[hanc].pop_back();
                //while (anc[hanc].size() && del[anc[hanc].back()]) anc[hanc].pop_back();
                //hav[hanc] = (anc[hanc].size() ? 1 : 0);
                int nf = anc[hanc][poi[hanc]]; poi[hanc] ++ ;
                hav[hanc] = (anc[hanc].size() > poi[hanc] ? 1 : 0);
                // 然后我们考虑 hanc -> nf 这个操作
                for (auto v : tr[f]){
                    if (del[v] || v == hanc) continue;
                    del[v] = 1, merge(f, v);
                }
                del[f] = 1, merge(f, f);
                // 剩下的就是，将 hanc 挂到 nf 底下
                // 这里是不是就是要改变 dep 了
                // 那我们 dep 排序的操作？
                // 注意到改变 dep 的时候 ndep != dep
                // 那么我们好像 dep[u] != d continue 就好了
                fa[hanc] = nf, dep[hanc] = dep[nf] + 1;
                tr[nf].push_back(hanc);
                //q.push({hanc, fa[hanc]});
                q.push({dep[hanc], hanc});
            }
        }

        vector <int> col(n + 1, 0); int omg = 0;
        for (int i = 1; i <= n; i ++ ){
            int qwq = find(i); assert(qwq != 0);
            if (!col[qwq]) col[qwq] = ++ omg;
            cout << col[qwq] << " ";
        }
        cout << "\n";
    }

    for (int i = 1; i <= n; i ++ ) g[i].clear(), tr[i].clear(), anc[i].clear();
    for (int i = 1; i <= n; i ++ ) fa[i] = dep[i] = del[i] = p[i] = hav[i] = poi[i] = 0;
}

bool end_mem;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T = 1;
    cin >> T;
    while (T -- ) init(), solve();

    cerr << "Memory AwA " << fixed << setprecision(13) << abs(&begin_mem - &end_mem) / 1024.0 / 1024.0 << " Mb.\n";
    cerr << "Memory AwA " << fixed << setprecision(13) << abs(&begin_mem - &end_mem) / 1024.0 / 1024.0 / 1024.0 << " Gb.\n";
}

/*
 * 
 * 10:35
 * 12:55
 * 
 * 
 */