LOJ2406 「THUPC 2017」母亲节的礼物 / Gift

题目链接：#2406. 「THUPC 2017」母亲节的礼物 / Gift

题意：

cxy 喜欢图，尤其是边数不太多的无向简单图。母亲节快到了，cxy 在纸上画了一张有 \(n\) 个节点、\(m\) 条边的无向简单图（即不存在重边、自环），保证每个点只和最多 \(7\) 个点相邻。接着，他想用 \(4\) 种不同的颜色给图中的节点进行染色，作为妈妈的母亲节礼物送给她。

cxy 希望染色之后的图尽量漂亮，他觉得相同颜色的点连成一片不好看。所以，他希望能给每对相邻的节点染上不同的颜色。遗憾的是，cxy 很快发现，在有些图中，这是不可能做到的。他不得不降低要求：每个点相邻的点中，至多有一个点和它的颜色相同。

限制条件放松了，问题也就变得简单了；但是 cxy 忙着做大作业，所以来找你帮忙。现在，请你告诉 cxy，是否能给图中每个点染上一个恰当的颜色，恰好满足 cxy 的要求？如果可以，请你给他指出一种染色方案；否则，只好残忍地告诉 cxy：impossible。

输入格式：

输入有多组数据，第一行一个整数 \(T(1\leq T\leq 10)\)，表示数据组数。

对于每组数据：

第一行两个整数 \(n,m(1\leq n\leq 25000,1\leq m\leq 100000)\)，分别表示图的点数和边数（约定点从 \(1\) 开始标号）。

接下来 \(m\) 行，每行两个整数 \(x,y(1\leq x,y\leq n)\)，描述图中的一条边，保证不存在重边、自环。

保证在一个输入文件中，有 \(\sum n\leq 200000,\sum m\leq 800000\)。

输出格式：

我们用小写英文字母 \(\mathtt{abcd}\) 给四种不同的颜色标号。

对于每组数据：

如果有解，输出一行一个长度为 \(n\) 的字符串 \(S\)，其中 \(S_i\) 表示你给第 \(i\) 个点染上的颜色（下标从 \(1\) 开始）；

否则，输出 impossible。

特殊性质是度数不超过 \(7\) ，而颜色只有 \(4\) 种。

则与节点 \(u\) 相邻的点中至少有一个点的颜色只出现了不超过一次，此时我们只需要另 \(u\) 为该颜色即可使其合法。

但是这可能导致其他的节点不符合条件，因此考虑递归处理这些点，于是我们可以得到一个这样的算法：

将原图随机染色为 \(G\) ，清空队列 \(q\) 。
找到 \(G\) 中的所有不合法节点 \(u\) ，即与 \(u\) 相邻的点中，至少 \(2\) 个点与 \(u\) 同色。
若 \(q = \varnothing\) ，则转到步骤 6，否则弹出队首 \(u\) 。若 \(u\) 已经是合法节点，重复步骤 3。
否则 \(u\) 的零点中必存在一种颜色 \(c_0\) ，其出现次数不超过 \(1\) 次。令 \(c(u) \gets c_0\) 。
遍历其邻点，若发现合法点变为不合法点，则将其加入队列 \(q\) ，并返回步骤 \(3\)
此时的图 \(G^{\prime}\) 已是原图的一个合法 \(4-\!\) 染色。

分析一下时间复杂度。考虑每次修改的增量。设 \(K(G)\) 为 \(G\) 中同色边的数量

设点 \(u\) 的邻点为 \(c_1,c_2,\cdots\) ，设 \(k(k \ge 2)\) 个点与 \(u\) 的颜色相同，而更改后，邻点中至多不超过 \(1\) 个与 \(u\) 同色

则每轮的增量为 \(\Delta K(G) \le 1 - k \le -1\) ，而初始 \(K(G) \le m\) ，最终的 \(K(G) \ge 0\) ，则操作数为 \(\mathcal{O}(m)\)

因此时间复杂度为 \(\mathcal{O}(n+m\Delta(G))\) ，其中 \(\Delta(G)\) 为 \(G\) 的最大度，数值上等于 \(7\) 。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

mt19937 rd(time(0));
int n,m,deg[N]; char col[N],inq[N];
vector<int> vec[N]; queue<int> q;
void clear()
{
    for(int i = 1; i <= n; i++) {
        vec[i].clear(); vec[i].shrink_to_fit(); deg[i] = col[i] = 0;
    }
}
void Modify(int u,int c)
{
    int old = col[u]; col[u] = c; deg[u] = 0;
    for(auto v : vec[u]) {
        if(col[v] == old) --deg[v];
        if(col[v] == c && (++deg[u], ++deg[v] >= 2) && !inq[v]) {
            q.push(v); inq[v] = 1;
        }
    }
}
void solve()
{
    cin >> n >> m; clear(); 
    for(int i = 1, u,v; i <= m; i++) {
        cin >> u >> v;
        vec[u].emplace_back(v); vec[v].emplace_back(u);
    }
    for(int i = 1; i <= n; i++) col[i] = rd() & 3;
    for(int u = 1; u <= n; u++)
    {
        for(auto v : vec[u]) deg[u] += (col[u] == col[v]);
        if(deg[u] >= 2) { q.push(u); inq[u] = 1; }
    }
    for(int u,cur; !q.empty(); )
    {
        u = q.front(); q.pop(); inq[u] = cur = 0; if(deg[u] < 2) continue;
        for(auto v : vec[u]) cur += (1 << (col[v] * 3));
        for(int i = 0; i < 4; i++) if(!(cur >> (i * 3 + 1) & 3)) { Modify(u,i); break; }
    }
    for(int i = 1; i <= n; i++) { col[i] += 'a'; } col[n + 1] = 0; cout << (col + 1) << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}