lessons/课程/07-二分图/01-二分染色与构造选择.md

二分图：染色、不变量与构造选择

本节目标

学完后，你应能用奇环刻画二分图，处理非连通分量的两种翻转选择，并把“每点只能做源或汇”“三标签相邻差 1”等构造条件还原成二分染色。

前置知识与课前自测

前置：BFS/DFS、连通分量、0/1 背包。

1. 一个图可二染当且仅当没有什么结构？
2. 每个连通二分分量的染色是否唯一？
3. 给无向边定向后，怎样保证不存在长度 2 的有向路径？

自测答案

1. 奇环。 2. 在整体翻转两侧颜色的意义下唯一；非连通图每个分量可独立翻转。 3. 让每个点要么所有边都出、要么所有边都入；相邻点必须属于相反类型。

问题动机与核心知识

从任一点染 0，沿边交替染色。遇到同色边时，DFS/BFS 树上两条到根路径与该边形成奇环；反之奇环无法交替回到起点原色。因此“可二染”和“无奇环”充要。

一个连通分量的两侧集合记为 $A_i,B_i$。所有合法二染只能选“$A_i$ 为颜色 0”或整体交换。若题目还规定某颜色恰有 $K$ 个点，就转成从每个分量选择 $|A_i|$ 或 $|B_i|$ 的分组背包，并保存决策恢复方案。

实现指南

• 颜色初始化为 -1，非连通图从每个未染点启动。
• 孤立点也是一个分量，两侧大小可视为 1 与 0。
• 恢复背包时记录“到达和 $s$ 的分量选择”，不能只有可达布尔值。
• 构造输出必须回到原输入顺序；保存边端点或对象编号。

精选例题 1：Graph Without Long Directed Paths

来源信息与题意

• VJudge：CodeForces-1144F Graph Without Long Directed Paths
• 原题：Codeforces Round 550 (Div. 3)
• 难度：1700；考点：二分图充要性、边定向输出

连通简单无向图有 $n,m\le2\times10^5$。给所有边定向，使有向图中不存在长度至少 2 的路径；若可行，按输入边输出 0/1 方向串。

Hint 1

若某点同时有入边和出边，就立刻出现长度 2 路径。

Hint 2

因此每个点必须是“纯源”或“纯汇”，相邻点类型相反。

Hint 3

二分染色后统一从颜色 0 指向颜色 1。

Observations、Editorial 与证明

不存在长度 2 路径等价于没有点同时作为某条边终点和另一条边起点，所以每点必须纯入或纯出，邻点类型相反，原图必须二分。若二分，所有边从一侧指向另一侧，任一有向路径走一步就到纯汇，无法继续，构造成立。

时间 $O(n+m)$，输出位由输入方向与颜色比较决定。

核心伪代码与参考实现附件

two-color the graph
if an edge has equal-colored endpoints: output NO
otherwise orient every edge from color 0 to color 1
translate each orientation back to a 0/1 character in input order

完整 GNU C++17 参考实现见附件：CodeForces-1144F.cpp

复盘与变式

若只要求无有向环，可以按任意顶点序给边从小到大定向，并不要求二分；“禁止长度 2”远强于“禁止环”。

精选例题 2：Graph Coloring

来源信息与题意

• VJudge：CodeForces-1354E Graph Coloring
• 原题：Educational Codeforces Round 87
• 难度：2100；考点：分量二染、分组背包、构造恢复

简单无向图有 $n\le5000,m\le10^5$，需恰用 $n_1,n_2,n_3$ 个标签 1、2、3，并使每条边两端标签差恰为 1。输出任一方案或 NO。

Hint 1

边只可能连接 1–2 或 2–3，所以标签 2 与非 2 构成二分两侧。

Hint 2

每个连通分量必须选择其中一侧全标 2；目标是总数恰为 $n_2$。

Hint 3

对各分量两侧大小做 0/1 分组背包，并保存选择。

Hint 4

剩余点之间没有边，可任取 $n_1$ 个标 1，其余标 3。

Observations、Editorial 与证明

任意边必须一端为 2，另一端为 1/3，所以图必须二分，且每个连通分量的某一整侧为 2。背包选择各分量哪侧，使总大小 $n_2$。选定后，所有非 2 点只与 2 相邻，它们之间无边，故任取 $n_1$ 个标 1 不会破坏条件。

反之任何合法标号诱导上述二分与分量选择，所以算法充要。染色 $O(n+m)$，背包 $O(n^2)$，适合 $n=5000$。

核心伪代码与参考实现附件

two-color every connected component and store its two sides
group-knapsack: from each component choose one side so total chosen size is n2
recover choices; label chosen side 2
among all remaining vertices label any n1 as 1 and the rest as 3

完整 GNU C++17 参考实现见附件：CodeForces-1354E.cpp

实现细节与复盘

choice[i][sum] 保存到达状态时第 $i$ 个分量选哪侧；同一状态被覆盖无妨，只需恢复任一路径。need3 由总数自动满足，但读入保留以对应题意。

精选例题 3：Arpa’s overnight party

来源信息与题意

• VJudge：CodeForces-741C Arpa’s overnight party and Mehrdad’s silent entering
• 原题：Codeforces Round 383 (Div. 1)
• 难度：2600；考点：构造辅助边、偶环二染

$n\le10^5$ 对情侣坐在环形排列的 $2n$ 张椅子上，每椅恰一人。给每人两种食物，要求情侣不同，且任意连续三人不能全相同。输出方案。

Hint 1

若强制椅子 `(1,2),(3,4),...` 中两人不同，则任意连续三椅必包含这样一对。

Hint 2

再给每对情侣连“必须不同”边。每个椅子恰连一条固定相邻边和一条情侣边。

Hint 3

所得多重图每点度数为 2，分量是偶环（两类边交替），可二染。

Observations、Editorial 与证明

建立 $2n$ 个椅子点，加入情侣边与固定配对边 $(1,2),(3,4),\ldots$。每点各属于一条两类边，所以沿环行走两类边交替，所有环长度为偶数，必可二染。二染保证情侣不同，也保证每个固定椅对不同；任意三个连续椅子中包含一个完整固定对，因此不会三人同色。

复杂度 $O(n)$。情侣恰坐固定对时会出现两条平行边，但不影响二染。

核心伪代码与参考实现附件

make one vertex for each chair
add an inequality edge for every romantic pair
add inequality edges (1,2), (3,4), ...
two-color every resulting even-cycle component
output the two colors at each romantic pair's chair positions

完整 GNU C++17 参考实现见附件：CodeForces-741C.cpp

复盘与变式

技巧不是“任意把相邻椅子配对”，而是选一组不交叠相邻对，使每个长度 3 窗口至少覆盖一对。若椅子数为奇数，这种完美配对不存在，构造需重新设计。

扩展与联系

高阶例题：Choosing Points

来源信息与题意

• VJudge：AtCoder-agc025_d Choosing Points
• 原题：AtCoder Grand Contest 025 D
• 难度：AGC 800 分；考点：距离图二染、数论奇偶性、两次染色取交

给定 $N,D_1,D_2$，其中 $1\le N\le300$，$1\le D_1,D_2\le2\times10^5$。从所有满足 $0\le x,y<2N$ 的格点中选出 $N^2$ 个，使任意两点的距离都不等于 $\sqrt{D_1}$ 或 $\sqrt{D_2}$。

这题的难点不是搜索点集，而是证明每一种平方距离都能把整张格点图切成两侧。

Hint 1：先只禁止一个距离

把每个格点看成点，距离平方为 $D$ 的两点连边。若能把这张图二染，同色点集就不会包含禁边。

Hint 2：距离平方的模 4 信息

若 $D$ 为奇数，则 $\Delta x,\Delta y$ 一奇一偶；若 $D\equiv2\pmod4$，则二者都为奇数。分别考虑 $(x+y)\bmod2$ 与 $x\bmod2$。

Hint 3：$4\mid D$ 怎么办

$\Delta x^2+\Delta y^2\equiv0\pmod4$ 强迫 $\Delta x,\Delta y$ 都是偶数。把坐标同时除以 2，问题缩成距离平方 $D/4$；点的颜色可以递归地由 $(\lfloor x/2\rfloor,\lfloor y/2\rfloor)$ 决定。

Hint 4：同时禁止两个距离

分别得到两位颜色 $(c_1,c_2)$，把 $4N^2$ 个格点分进四个桶。鸽巢原理保证某桶至少有 $N^2$ 个点。

Observations

1. 直接贪心选点需要动态检查大量平方距离；更重要的是，它解释不了题目保证的“任意 $D_1,D_2$ 都有解”。改看禁距图后，目标变成找一个大独立集。
2. 一般图的最大独立集仍然困难；本题真正删掉搜索的是“每个禁距图都可显式二染”。只禁止 $D$ 时，同一颜色类天然是独立集。
3. $D$ 的全部素因子并不重要。不断删除因子 4 后，只剩“奇数”或“模 4 余 2”两种奇偶骨架；它们分别由棋盘色和横坐标奇偶处理。
4. 对两个禁距图不必求公共独立集。两次二染交叉成四类，同一类在两张图中都独立；四类平均大小恰为 $N^2$。

Editorial、正确性与复杂度

定义 color(x,y,D)：只要 $4\mid D$，就令 $D\leftarrow D/4$ 且 $x\leftarrow\lfloor x/2\rfloor,y\leftarrow\lfloor y/2\rfloor$。终止后：

• 若 $D$ 为奇数，返回 $(x+y)\bmod2$；
• 若 $D\equiv2\pmod4$，返回 $x\bmod2$。

证明它是距离图的合法二染。设两格点差为 $(u,v)$ 且 $u^2+v^2=D$。当 $4\mid D$ 时，平方模 4 只能是 0 或 1，因此 $u,v$ 必须同为偶数；约去 2 后仍是同一形式。约分终止后，若 $D$ 奇，则 $u,v$ 一奇一偶，$(x+y)$ 奇偶必翻转；若 $D\equiv2\pmod4$，则 $u,v$ 都奇，$x$ 奇偶必翻转。因此每条距离平方为 $D$ 的边两端异色。

对 $D_1,D_2$ 分别算颜色，把点放入编号 2*c1+c2 的桶。同桶两点在两种染色下都同色，故不可能相距 $\sqrt{D_1}$ 或 $\sqrt{D_2}$。总点数为 $(2N)^2=4N^2$，至少一个桶有 $N^2$ 个点，取其中任意 $N^2$ 个即可。这同时证明构造不漏解目标，也说明无需尝试不同起点或回溯。

枚举格点的时间为 $O(N^2\log\max(D_1,D_2))$，空间为 $O(N^2)$；递归层数只等于因子 4 的个数。

核心伪代码与参考实现附件

function color(x, y, D):
    while D % 4 == 0:
        D = D / 4
        x = floor(x / 2)
        y = floor(y / 2)
    if D is odd:
        return (x + y) % 2
    return x % 2

make four empty buckets
for x in 0 .. 2*N-1:
    for y in 0 .. 2*N-1:
        key = 2*color(x,y,D1) + color(x,y,D2)
        append (x,y) to bucket[key]
output any N*N points from a bucket whose size is at least N*N

完整 GNU C++17 参考实现：AtCoder-agc025_d.cpp

实现细节、复盘与变式

• 这里除的是点坐标本身的整数商；对一条实际禁距边，两端在每层的坐标差都是偶数，所以该染色证明不受低位舍弃影响。
• 不要枚举满足 $u^2+v^2=D$ 的位移，颜色公式已经同时处理全部位移。
• 识别信号是“两个关系各自可二染，但需要同时独立”；可迁移方法是取颜色向量，再用鸽巢原理选最大交类。
• 若禁距数增加到 $k$ 个，同样会得到 $2^k$ 个桶，只能保证最大桶至少有总点数的 $2^{-k}$；本题的常数 2N 正好与两个约束匹配。

扩展与联系

• 二分图判定也可返回一条奇环作为不可行证据：遇到同色边后沿 BFS 父链找公共祖先。
• 分量翻转 + 背包是常见结构，出现“每块二选一且总量固定”应主动识别。
• 2-SAT 能表达更一般的二选一冲突；本节图染色是其更特殊且更快的情形。

总结与自检

1. 同色边怎样构造奇环证据？
2. 无长度 2 有向路径为何等价于纯源/纯汇二分？
3. 三标签题为什么标签 2 必须占每个分量完整一侧？
4. 派对题新增固定配对边解决了哪个瓶颈？

课后训练建议

第一题应独立完成；第二题先只求是否能选出 $n_2$，再加恢复；第三题不看代码手画 3 对情侣的辅助图。复盘时把每题的“二分两侧分别代表什么”写成一句语义，而不是只写颜色 0/1。