01-二分染色与构造选择.md 8.2 KB
二分图：染色、不变量与构造选择
本节目标
学完后，你应能用奇环刻画二分图，处理非连通分量的两种翻转选择，并把“每点只能做源或汇”“三标签相邻差 1”等构造条件还原成二分染色。
前置知识与课前自测
前置：BFS/DFS、连通分量、0/1 背包。
- 一个图可二染当且仅当没有什么结构？
- 每个连通二分分量的染色是否唯一？
- 给无向边定向后，怎样保证不存在长度 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 窗口至少覆盖一对。若椅子数为奇数，这种完美配对不存在，构造需重新设计。
扩展与联系
- 二分图判定也可返回一条奇环作为不可行证据：遇到同色边后沿 BFS 父链找公共祖先。
- 分量翻转 + 背包是常见结构，出现“每块二选一且总量固定”应主动识别。
- 2-SAT 能表达更一般的二选一冲突；本节图染色是其更特殊且更快的情形。
总结与自检
- 同色边怎样构造奇环证据？
- 无长度 2 有向路径为何等价于纯源/纯汇二分？
- 三标签题为什么标签 2 必须占每个分量完整一侧？
- 派对题新增固定配对边解决了哪个瓶颈？
课后训练建议
第一题应独立完成；第二题先只求是否能选出 $n_2$，再加恢复；第三题不看代码手画 3 对情侣的辅助图。复盘时把每题的“二分两侧分别代表什么”写成一句语义，而不是只写颜色 0/1。