BIPARTITE GRAPH · KNOWLEDGE BASE
二分图详解
从“两类对象之间的配对”出发，把二分图的判定、匹配、增广路、匈牙利算法、 Kőnig 定理与常见建模串成一张知识网。学完这一页，再看座位题和匹配题会顺畅很多。
01 · 直觉与定义
什么是二分图
二分图是一张“两类对象配对”的图：顶点分成左右两组 L 和 R，每条边都连接一个左顶点和一个右顶点，组内没有任何边。 男女配对、候选人与岗位、课程与教室、黑白棋盘上的相邻格，都是典型场景。
用两种颜色给顶点染色，相邻顶点必须异色。
图中不存在长度为奇数的环；奇环是二分图唯一的“障碍”。
边不是“认识”，而是“可以配对一次”的候选关系。
这三个说法是等价的：能二染色 ⇔ 无奇环 ⇔ 二分图。因此“判定一张图是不是二分图” 本质上就是检查它能否被二染色。
02 · 判定
二染色：BFS/DFS 检查冲突
从一个未染色顶点开始，把它染成颜色 1，邻居必须染成颜色 2，再递归下去。 如果某个邻居已经染过且与当前顶点同色，就说明存在奇环，不是二分图。 注意图可能不连通，每个连通块都要检查。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> g[N];
int color[N]; // 0 未染色, 1 / 2 两种颜色
bool bfs(int s) {
queue<int> q;
color[s] = 1;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (color[v] == 0) {
color[v] = 3 - color[u]; // 相邻必须异色
q.push(v);
} else if (color[v] == color[u]) {
return false; // 冲突：存在奇环
}
}
}
return true;
}
int main() {
int n, m;
cin >> n >> m;
while (m--) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
if (color[i] == 0 && !bfs(i)) {
cout << "NO\n"; // 不是二分图
return 0;
}
}
cout << "YES\n";
return 0;
}复杂度 O(n+m)。识别信号：题目说“分成两组”“黑白染色”“互斥配对”， 或者要求判断是否存在奇环。
03 · 匹配基础
匹配、最大匹配与增广路
一组两两不相邻的边：每个顶点至多出现在一条匹配边里。
边数最多的匹配。注意最大匹配不一定唯一。
每个顶点都被匹配覆盖，边数恰好等于 |V|/2。
没有被任何匹配边覆盖的顶点。
从未盖点出发，匹配边、非匹配边交替出现的路径。
两端都是未盖点的交替路。把路径上的匹配/非匹配边翻转，匹配数 +1。
一个匹配是最大匹配，当且仅当图中不存在增广路。 每找到一条增广路并翻转路径上的匹配/非匹配边，匹配数就增加 1。
以候选人—岗位为例：把“已录取”看成匹配边。一个人如果被更合适的岗位吸引， 可以让原来占着那个岗位的人去别处——这就是增广路里的“让位”。
04 · 算法
匈牙利算法：用 DFS 找增广路
对左侧每个顶点做一次 DFS 尝试匹配：优先找未匹配的右点；如果右点已被匹配， 就递归尝试让它的原搭档换到别的右点。成功一次，匹配数 +1。
bool tryMatch(int u) {
for (int v : graph[u]) {
if (visited[v]) continue;
visited[v] = true;
// 岗位空闲，或者原搭档能“让位”到别处
if (matchRight[v] == -1 || tryMatch(matchRight[v])) {
matchRight[v] = u;
return true;
}
}
return false;
}
int maximumMatching(int leftCount, int rightCount) {
matchRight.assign(rightCount, -1);
int answer = 0;
for (int u = 0; u < leftCount; ++u) {
visited.assign(rightCount, false); // 每轮必须清空
if (tryMatch(u)) ++answer;
}
return answer;
}三个易错点：每轮 DFS 前必须清空 visited；matchRight[v] 存的是“右点 v 当前与哪个左点匹配”； 递归让位时要沿着原匹配边回到左点继续尝试。 数据量更大时可用 Hopcroft–Karp，复杂度 O(E√V)。
05 · 定理
Kőnig 定理与四个经典量
二分图中，最小点覆盖 = 最大匹配。 即用最少的顶点覆盖所有边，所需顶点数恰好等于最大匹配边数。
由 Kőnig 定理可以立刻推出下面四个量之间的关系（M 为最大匹配）：
| 最大匹配 | M | 边数最多的一对一配对 |
| 最小点覆盖 | = |M| | 用最少顶点覆盖所有边（Kőnig 定理） |
| 最大独立集 | = |V| − |M| | 点覆盖的补集：两两无边 |
| 最小边覆盖 | = |V| − |M| | 无孤立点时，用最少边覆盖所有顶点 |
| 最小边着色 | = Δ | 把边染成 Δ 组匹配（Kőnig 线染色） |
这些量经常互换：求“最多选几个互不冲突”其实是最大独立集， 而独立集 = 总顶点数 − 最大匹配；“最少选几个点覆盖所有关系”就是最小点覆盖。
06 · 应用
把现实问题建模成二分图
识别信号只有一句话：两类对象、一对一使用、每个对象至多用一次。 下面是最常见的九种建模。
APPLY 01
任务分配左侧任务、右侧工人，会做就连边。最多同时安排的任务数 = 最大匹配。
APPLY 02
候选人 · 岗位每个人最多一个岗位、每个岗位最多一个人，一次录取就是一条匹配边。
APPLY 03
棋盘放棋子（墙分割）墙把行切成横段、把列切成竖段；每个空格连接所在横段与竖段，放子即选边。
APPLY 04
多米诺覆盖棋盘黑白染色，相邻格异色。一块骨牌覆盖一黑一白；铺满即完美匹配。
APPLY 05
互不攻击的马马步只连接异色格，求最多放多少马等价于最大独立集 = 总格数 − 最大匹配。
APPLY 06
课程 · 教室左侧课程、右侧可用教室/时间槽，能安排就连边；判断能否全部排下。
APPLY 07
DAG 最小路径覆盖每个点拆成入点/出点，路径覆盖数 = |V| − 最大匹配。
APPLY 08
排班 / 调度两类资源（员工×班次、机器×订单）一对一使用，最大化利用率。
APPLY 09
二分图博弈某些删点/移动博弈中，先手是否必胜可由最大匹配的关键点判断。
07 · 学习路径