自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:00:05，当前版本为作者最后更新于2022-07-06 20:14:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Upd on 2022.7.7：修正代码，修改笔误。

*P4429 [BJOI2018] 染色

我花了一个下午和一个晚上研究这道结论题及其证明。现有题解的证明与推导过程太简略，并不严谨，且没能很好地体现本题的思维难度，希望我的题解能帮到大家。

如有笔误或难以理解的部分还请指出。

基本判断

显然，当 $G$ 不是二分图时无解，图上所有环均为偶环。

设 $G$ 连通，若 $G$ 不连通，其每个连通块独立，可分别求解。

度数为 $1$ 的点不产生贡献，因其可根据唯一邻点的颜色确定自身颜色，不可能无解，故不断剥去度数为 $1$ 的点，直到图上所有点度数 $\geq 2$。

固定

由样例可知若 $G$ 包含 $K_{3, 3}$ 则无解，但这个条件太强了，不必要。

尝试手玩 $K_{2, 2}$，即长度为 $4$ 的环 $(1, 2, 3, 4)$，目标是确定一些颜色，降低不确定性。

不失一般性，节点 $1$ 的颜色集合 $S_1 = \{A, B\}$。注意到 $3$ 与 $2, 4$ 相连，若给 $1$ 涂上颜色 $A$ 后，$2, 4$ 被迫选择 $B, C$，令 $S_3 = \{B, C\}$ 即可导出矛盾。根据推理，当 $S_1 = \{A, B\}$，$S_2 = \{A, B\}$，$S_3 = \{B, C\}$，$S_4 = \{A, C\}$ 时，可固定 $c_1 = B$。

尝试抽象出固定的本质。设节点 $i$ 及 $S_i = \{A, B\}$，「固定」需要两个「自由点」$j, k$，使得 $i$ 取某个颜色时，$j$ 不得不取某个 与 $i$ 不同 的颜色，而 $k$ 的颜色集与 $i, j$ 颜色重合，得到矛盾。

简单环

接下来讨论的环为不经过重复节点的 简单环。

一个环固定环上任意点颜色，只需再用一个环导出矛盾即可。因形如 “只能选两种颜色之一” 的限制可通过度数为 $2$ 的节点传播，故若 $G$ 存在两个不交的由一条链连接的环，则无解。

证明：考虑环 $C_1, C_2$ 及连接它们的路径 $P = u\to v$，其中 $u\in C_1$，$v\in C_2$。令 $P$ 上所有节点颜色集合为 $\{A, B\}$。固定 $c_u = A$，$c_v$ 根据 $|P|$ 奇偶性固定为 $A$ 或 $B$ 容易通过 $P$ 导出矛盾。证毕。

进一步地，若 $G$ 存在两个交于一点的环，则无解，此时 $P$ 退化为单点。例如在上例基础上添加环 $(1, 5, 6, 7)$，令 $S_5 = \{A, B\}$，$S_6 = \{A, C\}$，$S_7 = \{B, C\}$ 可固定 $c_1 = A$，矛盾。

两个四度点

注意到两个交于一点的环形成度数为 $4$ 的节点，设两个 $deg \geq 4$ 的节点 $u, v$。

若存在 $u\to v$ 的两条路径 $P_1, P_2$ 交于 $q_1, q_2, \cdots, q_k\neq u, v$，则 $C_1 = u\xrightarrow{P_1} q_1 \xrightarrow{P_2} u$ 与 $C_2 = v\xrightarrow{P_1} q_k\xrightarrow{P_2} v$ 至多交于一点 $q_1$，无解。

假设 $u\to v$ 某四条路径分别长 $L_1, L_2, L_3, L_4$。

当 $L$ 为奇数时，因无重边，故 $L_2, L_3, L_4 \geq 3$。因形如 “只能选某固定颜色” 的限制可通过度数为 $2$ 的节点 以 $2$ 为周期 传播，即讨论无解性时长 $k$ 的链可归约至长 $k - 2$ 的链，故只需考虑 $L_2 = L_3 = L_4 = 3$。根据固定的本质，读者容易自行构造反例。如果不会，见三度点部分 $(3, 3, 1)$ 反例，其强于 $(3, 3, 3)$。

当 $L$ 为偶数时，同理只需考虑 $L_1 = L_2 = L_3 = L_4 = 2$ 的 $K_{2, 4}$。令 $S_u = \{A, B\}$，$S_v = \{C, D\}$，中间四个点分别为 $\{A, C\}$，$\{A, D\}$，$\{B, C\}$，$\{B, D\}$ 即可。

因此，图上存在至少两个 $deg\geq 4$ 的节点时，无解。

一个四度点

当图上仅有一个 $deg\geq 4$ 的节点时，要么存在至少两个 $deg = 3$ 的节点，要么剩余所有节点 $deg = 2$。

对于后者，其形态为两个交于一点的环，无解。

对于前者，设两个 $deg = 3$ 的节点 $u, v$，同理可证 $u\to v$ 之间任意路径仅在 $u, v$ 处相交，与存在 $deg\geq 4$ 的节点矛盾。

因此，图上存在至少一个 $deg\geq 4$ 的节点时，无解。

接下来讨论不存在四度及以上节点的图。

三度点

讨论完四度点，让我们将目光转向三度点。一旦图上存在三度点的情况被讨论清楚，问题就迎刃而解。

考虑图上某两个三度点 $u, v$，上文已经说明 $u\to v$ 之间任意路径仅在 $u, v$ 处相交，故图上仅存在两个三度点。

设 $u\to v$ 三条路径长 $L_1, L_2, L_3$，$L_1 \geq L_2 \geq L_3$。

考虑 $L_3 = 1$。

因无重边，故 $L_1, L_2 \geq 3$。如法炮制，根据归约关系考虑 $L_1 = L_2 = 3$。根据固定的本质，在最开始例子的基础上，添加环 $(1, 2, 5, 6)$，令 $S_5 = \{A, C\}$，$S_6 = \{B, C\}$ 可固定 $c_1 = A$。无解，称为 $(3, 3, 1)$ 反例。

考虑 $L_3 = 2$。

从简单情况入手，考虑 $L_1 = L_2 = 2$ 的 $K_{2, 3}$。

• 若 $S_u\cap S_v \neq \varnothing$，则令 $c_u$ 和 $c_v$ 等于它们的交中的某个颜色，则中间三个点因为 $|S| = 2$，总可以选择不与该颜色相同的颜色，有解。
• 若 $S_u\cap S_v = \varnothing$，则 $c_u$ 与 $c_v$ 的颜色共有 $4$ 种不同情况，而每个节点只被唯一情况封锁住，所以至少有一种情况没有封锁住任何节点，有解。

这说明 $K_{2, 3}$ 有解。

进一步地，考虑 $L_1 \geq 4$。$K_{2, 3}$ 的讨论给予我们突破点：考虑 $c_u, c_v$ 的颜色情况数，与夹在中间的节点个数 $2$ 作比较。若情况数 $> 2$ 或 $c_u = c_v$ 则有解，否则无解。

• 若 $L_1$ 对应路径存在相邻两个点的 $S$ 不同，则当 $c_u$ 取两种颜色时，按照环边染色，$c_v$ 分别有两种和至少一种合法选择。
  • 若 $S_u\cap S_v \neq \varnothing$，存在三种不同情况，有解。
  • 若 $|S_u\cap S_v| = \{A\}$，若 $c_u = c_v = A$ 不合法，则剩余三种情况互不相同，有解；否则 $c_u = c_v = A$ 合法，有解。
  • 若 $S_u = S_v$，$c_u\neq c_v$ 的情况只有两种，必然存在 $c_u = c_v$ 合法的情况，有解。
• 否则，由于 $L_1$ 为偶数，所以 $c_u = c_v$，有解。

这说明仅有 $L_1 \geq 4$ 时仍然有解。

容易发现上述证明并没有用到 $L_1 \geq 4$ 的性质，即它可以用于证明 $K_{2, 3}$ 的有解性。但如果不先从 $K_{2, 3}$ 下手，不易想到情况数这一突破点。因此，从简单情况入手 是这种推性质题相当好用的解题技巧。

进一步地，考虑 $L_1, L_2\geq 4$。由于上文讨论过 $(3, 3, 1)$ 无解，不难再此基础上稍作修补，构造出使得 $(4, 4, 2)$ 无解的反例。提示：考虑固定的本质，$L_1, L_2 \geq 4$ 说明存在两组自由点 $j, k$，每组自由点可固定 $c_u$ 为某颜色。

综上，我们得到图上存在三度点有解的充要条件：图上仅存在两个三度点，且至少存在两个与两个三度点同时相邻的二度点。

偶环

最后，考虑仅存在二度点的图。因无重边，它是一个长度 $\geq 4$ 的环。

类似地，考虑环上相邻三个节点 $u, v, q$ 并最后考虑 $v$ 的限制。若 $u$ 从环的另一侧到 $q$ 的路径上 $S$ 相同，则 $c_u = c_q$ 合法，有解。否则考虑使得 $c_q$ 有两种染色方案的 $c_u$，无法封锁 $v$，有解。

结论

对 $G$ 的每个连通块单独求解，若存在连通块无解则整张图无解。

$G$ 有解当且仅当其为二分图，且满足以下性质之一：

• 不存在 $deg \geq 3$ 的点。
• 不存在 $deg \geq 4$ 的点，且仅存在两个三度点，且至少存在两个与三度点同时相邻的二度点。

容易在 $\mathcal{O}(m\log m)$ 或 $\mathcal{O}(m)$ 的时间进行上述判定。

代码

#include <bits/stdc++.h>
using namespace std;
bool Mbe;
constexpr int N = 1e4 + 5;
int n, m, GG, col[N];
set<int> e[N];
vector<int> G;
void dfs(int id) {
  G.push_back(id);
  for(int it : e[id]) {
    if(col[it] == -1) col[it] = col[id] ^ 1, dfs(it);
    else if(col[id] == col[it]) GG = 1;
  }
}
void solve() {
  GG = 0;
  cin >> n >> m;
  memset(col, -1, sizeof(col));
  for(int i = 1; i <= n; i++) e[i].clear();
  for(int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    e[u].insert(v), e[v].insert(u);
  }
  queue<int> q;
  for(int i = 1; i <= n; i++) if(e[i].size() == 1) q.push(i);
  while(!q.empty()) {
    int t = q.front();
    q.pop();
    if(e[t].empty()) continue;
    int it = *e[t].begin();
    e[t].clear(), e[it].erase(t);
    if(e[it].size() == 1) q.push(it);
  }
  for(int i = 1; i <= n; i++) if(e[i].size() > 3) return puts("NO"), void();
  for(int i = 1; i <= n; i++) {
    if(col[i] != -1) continue;
    col[i] = 0, G.clear(), dfs(i);
    if(GG) return puts("NO"), void();
    int u = -1, v = -1;
    for(int it : G)
      if(e[it].size() == 3) {
        if(u == -1) u = it;
        else if(v == -1) v = it;
        else return puts("NO"), void();
      }
    if(u != -1) {
      int cnt = 0, c[3], d[3];
      for(int i : {0, 1, 2}) {
        c[i] = *e[u].begin(), e[u].erase(e[u].begin());
        d[i] = *e[v].begin(), e[v].erase(e[v].begin());
      }
      for(int i : {0, 1, 2}) for(int j : {0, 1, 2}) cnt += c[i] == d[j];
      if(cnt < 2) return puts("NO"), void();
    }
  }
  puts("YES");
}
bool Med;
int main() {
  fprintf(stderr, "%.4lf\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
  #endif
  int T;
  cin >> T;
  while(T--) solve();
  return cerr << "Time: " << clock() << "\n", 0;
}
/*
2022/7/6
start thinking at 9:57
首先图必须得是二分图。
再加上不存在 K{3, 3} 是否是充要条件？
Try a try, AC is OK.
不是。
冷静分析了一下，可能是 K{2, 3}。
不是。
好像是两个并列简单环。
很神仙的题目，研究了一下午。
start coding at 17:10
finish debugging at 17:18
*/