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

> 先完成 [课前零食：两支队伍与奇怪的圈](00-课前零食-两支队伍与奇怪的圈.md)，再把“奇环冲突”带进构造题。

## 本节目标

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

## 前置知识与课前自测

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

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

<details><summary>自测答案</summary>

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

</details>

## 问题动机与核心知识

从任一点染 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](https://vjudge.net/problem/CodeForces-1144F)
- 原题：[Codeforces Round 550 (Div. 3)](https://codeforces.com/problemset/problem/1144/F)
- 难度：1700；考点：二分图充要性、边定向输出

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

<details><summary>Hint 1</summary>若某点同时有入边和出边，就立刻出现长度 2 路径。</details>
<details><summary>Hint 2</summary>因此每个点必须是“纯源”或“纯汇”，相邻点类型相反。</details>
<details><summary>Hint 3</summary>二分染色后统一从颜色 0 指向颜色 1。</details>

### Observations、Editorial 与证明

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

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

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

```text
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](../../参考实现/07-二分图/CodeForces-1144F.cpp)

### 复盘与变式

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

## 精选例题 2：Graph Coloring

### 来源信息与题意

- VJudge：[CodeForces-1354E Graph Coloring](https://vjudge.net/problem/CodeForces-1354E)
- 原题：[Educational Codeforces Round 87](https://codeforces.com/problemset/problem/1354/E)
- 难度：2100；考点：分量二染、分组背包、构造恢复

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

<details><summary>Hint 1</summary>边只可能连接 1–2 或 2–3，所以标签 2 与非 2 构成二分两侧。</details>
<details><summary>Hint 2</summary>每个连通分量必须选择其中一侧全标 2；目标是总数恰为 $n_2$。</details>
<details><summary>Hint 3</summary>对各分量两侧大小做 0/1 分组背包，并保存选择。</details>
<details><summary>Hint 4</summary>剩余点之间没有边，可任取 $n_1$ 个标 1，其余标 3。</details>

### Observations、Editorial 与证明

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

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

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

```text
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](../../参考实现/07-二分图/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](https://vjudge.net/problem/CodeForces-741C)
- 原题：[Codeforces Round 383 (Div. 1)](https://codeforces.com/problemset/problem/741/C)
- 难度：2600；考点：构造辅助边、偶环二染

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

<details><summary>Hint 1</summary>若强制椅子 `(1,2),(3,4),...` 中两人不同，则任意连续三椅必包含这样一对。</details>
<details><summary>Hint 2</summary>再给每对情侣连“必须不同”边。每个椅子恰连一条固定相邻边和一条情侣边。</details>
<details><summary>Hint 3</summary>所得多重图每点度数为 2，分量是偶环（两类边交替），可二染。</details>

### Observations、Editorial 与证明

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

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

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

```text
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](../../参考实现/07-二分图/CodeForces-741C.cpp)

### 复盘与变式

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

## 扩展与联系

## 高阶例题：Choosing Points

### 来源信息与题意

- VJudge：[AtCoder-agc025_d Choosing Points](https://vjudge.net/problem/AtCoder-agc025_d)
- 原题：[AtCoder Grand Contest 025 D](https://atcoder.jp/contests/agc025/tasks/agc025_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}$。

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

<details><summary>Hint 1：先只禁止一个距离</summary>

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

</details>

<details><summary>Hint 2：距离平方的模 4 信息</summary>

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

</details>

<details><summary>Hint 3：$4\mid D$ 怎么办</summary>

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

</details>

<details><summary>Hint 4：同时禁止两个距离</summary>

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

</details>

### 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 的个数。

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

```text
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](../../参考实现/07-二分图/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。