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;
}