00-课前零食-两支队伍与奇怪的圈.md 11 KB
课前零食：两支队伍与奇怪的圈
如果所有“不能同队”的关系都能安排成左队和右队，图就是二分图。听起来像排座位，真正的捣蛋鬼却是一种很具体的结构：奇数长度的圈。
本节目标
学完后，你能：
- 把二分图理解成“每条边都跨越两种颜色”的图；
- 用 BFS/DFS 的交替染色法判定二分图，并从同色冲突找到奇环；
- 说明为什么一个连通二分分量的两种染色只差整体翻转；
- 为正式课中的构造、匹配与 Kőnig 定理准备“左右两侧”的模型。
前置知识与课前自测
前置：无向图、BFS/DFS、连通分量。
- 一条边的两个端点若必须异色，走过两条连续边后颜色会变成原色还是另一色？
- 三角形能否被两种颜色染得每条边两端不同？
- 一个孤立点放左边还是右边会影响已有边的合法性吗？
答案
1. 变回原色。2. 不能：第三条边会连接同色点。3. 不会；它本身就是一个可自由翻转的小分量。互动规则：每条边都是一句“你们不能同色”
先不要把颜色当漂亮的涂料。给每个点留一个格子，填 未定 / 0 / 1；每处理一条边，就把它读成约束：“若 u 是 0，v 必须是 1。”纸上同时记录 是谁迫使谁染色，这样冲突时才能沿证据回去找圈。
本节只有一个框架问题：局部的“不同”约束能否一路传播而不自相矛盾？先让自己撞到矛盾，再给它正式名字“奇环”。
从零搭框架：从猜所有队伍到让边替你决定
第 0 步：先用两种颜色安排一条链
画路径 A-B-C-D。任意给 A 涂 0，沿边依次写出其余颜色。然后把最后一条边 D-A 加上，观察结果；再把路径改为 A-B-C-A。
停顿 0：为什么长度为 4 的环可以回到 A 的原色，而长度为 3 的环会要求 A 既是 0 又是 1？请逐边写颜色，不要直接说“奇环”。
展开：每走一步都翻转一次
走一条边颜色翻转；偶数步回到原色，奇数步回到反色。偶环最后的约束与起点一致，奇环最后一条边却要求起点异于自己，矛盾。这就是奇环不能二染的最小原因。第 1 步：让 BFS/DFS 只做约束传播
画边 A-B,A-D,C-B,C-D,E-F。从 A 开始，给 A 染 0；每遇到未染邻点就染反色。请填写：
| 当前取出的点 | 它的颜色 | 看到的未染邻点 | 给出的颜色 | 父亲证据 |
|---|---|---|---|---|
| A | 0 | |||
| B | 1 | |||
| E | 0 |
停顿 1：为什么处理完 A 所在分量后，仍要从 E 重新开始？
visited与color在这里分别负责什么？
展开：颜色是带内容的访问标记
边无法把消息传到另一个连通分量，所以每个未染点都要自立门户。`color=-1` 同时表示未访问；0/1 不只表示访问过，还记录它相对根的路径长度奇偶。最终两侧为 `{A,C,E}` 与 `{B,D,F}`，每个分量可整体翻转。第 2 步：让同色冲突自己画出一条奇环
在图 A-B,B-C,C-A,C-D 中，从 A 染 0。你会得到 B、C 都是 1，然后检查边 B-C。请保存每个点的父亲：parent[B]=A,parent[C]=A。
停顿 2：从 B 沿父亲回根、从 C 沿父亲回根，再加冲突边 B-C，会得到哪一圈？为什么它长度是奇数？
展开：冲突边是一份反例证书
得到 `B→A→C→B`。B、C 同色意味着它们到共同根的路径长度同奇偶；两条树路径合起来是偶数长度，再加一条冲突边便是奇数。算法不仅说“不行”，还给出一条能拿在手里的奇环。第 3 步：一个连通分量为什么只有两个可选方案
把可二染分量的根 A 从 0 改成 1，不重新搜索，只把所有点颜色翻转。请检验每条边是否仍跨色。然后试图只翻转 C，观察哪条边先坏。
停顿 3：题目若要求恰好 K 个点在左侧，为什么不能把每个点随意改色？真正可自由选择的单位是什么？
展开：自由度在分量层，不在点层
连通分量内任一点颜色被根到它的路径奇偶固定，只有根的初始色能选；因此一个分量只有“当前分法”与“整体翻转”两种。多个分量才给出多次独立选择，正式课会把这些选择接到背包与构造恢复上。第 4 步：把两侧理解成角色，而不只是颜色
若边表示“左侧任务可交给右侧机器”，或“相邻点不能同组”，请分别写出颜色 0/1 在题面中的角色。再问：若输入本身已经把对象分成男/女、工人/任务两类，还需要先跑二染吗？
展开：二分图是关系的类型检查
有天然两类时，先检查边是否都跨类；没有天然两类时，染色在发明两类。后续匹配只允许跨两侧配对，所以“能否二染”常是把题面关系变成左右接口的第一步。问题动机：逐边猜队伍会有 $2^n$ 种选择
给每个点猜“左/右”看似简单，但 $n$ 个点有 $2^n$ 种分配。边提供了更强的传播规则：给一个起点染 0，沿每条边的另一端必须是 1，再沿下一条边又必须是 0。一次 BFS/DFS 就能把一个连通块的所有颜色推出来。
真正需要检查的是：某条边的两端会不会被迫同色。若会，沿 BFS/DFS 树从两端回到共同祖先，再加上这条冲突边，正好得到一个奇环。
步步式引导
1. 为什么奇环一定失败
沿一个环交替染色。走偶数步回到起点会要求原色；走奇数步回到起点却要求反色，矛盾。所以任何奇环都不是二分图。
反过来，若交替染色遇到同色边 $(u,v)$，DFS/BFS 树上从根到 $u$、从根到 $v$ 的路径长度同奇偶；两条路径加这条边形成奇环。因此“能二染”与“没有奇环”是充要关系，而不是一条单向小技巧。
color[all] = UNCOLORED
for every vertex start:
if color[start] is UNCOLORED:
color[start] = 0
queue.push(start)
while queue not empty:
u = queue.pop_front()
for v in neighbors[u]:
if color[v] is UNCOLORED:
color[v] = 1 - color[u]
queue.push(v)
else if color[v] == color[u]:
report "not bipartite"
纸上模拟：一边传播，一边保留冲突证据
对 A-B,B-C,C-A,C-D，从 A=0 开始，填写：
| 队列取出 | color 已知值 |
处理的边 | 采取动作 | parent 新记录 |
|---|---|---|---|---|
| A | A-B | |||
| A | A-C | |||
| B | B-C |
然后在另一个纸面上给 A-B,A-D,C-B,C-D,E-F 染色；把两个分量的两侧大小写为 (2,2) 与 (1,1)，试着整体翻转其中一个。
展开：算法状态与题目后续选择
第一张图在 B-C 处发现同色冲突，并用父亲恢复三角形。第二张图无冲突，第一分量左右均 2，第二均 1；翻转不破坏任何边，只交换每个分量给全局左侧贡献的大小。颜色传播解决可行性，分量翻转保留构造自由度，两件事不要揉成一团。2. 一个分量为什么只有两种方案
确定根的颜色后，任一点到根的路径长度奇偶决定其颜色；若图无奇环，任意两条路径的奇偶不会矛盾。因此整个连通分量只有“当前 0/1 分配”和“全部交换 0/1”两种选择。多个分量互不影响，才会出现“每团选左还是右”的背包或构造问题。
3. 从两支队伍到匹配
二分匹配只在左右两侧间配对：一条边表示“这个左对象可以和这个右对象搭档”。今天不求最大匹配，只先练模型辨认：若对象天然有两类、关系只应跨类出现，先检查二分结构；若图不是二分图，别急着套匹配。
核心知识：颜色是边约束传播后的证书
color[u] 不是一个随便的标签，而是“从起点到 $u$ 的路径长度奇偶”的证书。每次把未染邻点设成反色，都满足当前边；遇到同色边则给出不可行的具体证据。全图要从每个未染点启动，因为非连通分量没有边替你传话。
时间和空间都是 $O(V+E)$。自环立即连接同一点与自己，强迫它与自己异色，因此是最短的奇环；重边不会破坏二分性，只是重复检查同一约束。
实现指南
- 用
-1表示未染，避免把颜色 0 误当“没访问”。 - 保存
parent和depth能在冲突时还原一个奇环，调试非常有用。 - 题目若要求两侧人数恰好为某值，不能随意固定每个分量的方向；要保留“翻转”选择。
- 有向图题若问相邻端点能否分两类，通常先忽略方向判断底层无向图，但必须看题意是否允许这样做。
互动小实验室
运行 两支队伍与奇怪的圈.py。选择 g 看一个可二染图如何分左右两侧；选择 b 看一条同色冲突边如何还原奇环。也可输入自己的无向边表。
建议先挑一个三角形，试图亲手给三点染色；当第三条边开始抗议时，再让程序把它说出来。
扩展与联系
连通二分分量的翻转会通向分组背包；交替路径会通向二分匹配；“没有奇环”还会出现在图的奇偶约束和差分建模中。若边约束不只是“不同”，例如要求颜色差为某个模数，就需要更一般的带权并查集或图染色工具。
总结与自检
- 同色冲突边为什么会构成奇环证据？
- 为什么每个连通分量只能整体翻转，不能单独翻一个点？
- 自环为什么直接否定二分性？
自检答案
两端到根深度同奇偶，树路径合起来再加冲突边长度为奇数；边会把所有点的相对颜色固定；它要求同一点异于自己。一周预热安排
- 第 1 天：给路径、偶环、奇环各手染一次。
- 第 2 天：练习从同色边画回奇环。
- 第 3 天：把两个不连通分量的两侧翻转写成选择表。
- 第 4 天：运行互动程序，输入含自环或重边的图。
- 第 5 天：进入二分染色与构造选择正式课。