本讲定位：图论系列第十五讲。前两讲（13 SCC、14 割点割边）共用一套
dfn/low，本讲完全离开它，换一个新问题：能不能把点分成两组，使每条边的两个端点都跨组？ 这个问题本身只需要十行染色代码，但它引出的最大匹配和 König 定理，能把一堆看起来毫不相关的题——棋盘放骑士、矩阵行列交换、任务分配、DAG 路径覆盖——统一成同一个模型。本讲做了十二组实测，四个数字值得先记住：匈牙利算法里vis只在最外面清一次，小图上错 12.66% 且永远只会偏小，但在大随机图上只少 0.2%~1.7% 的匹配——这就是”写错了却过了样例甚至过了大部分测试点”的来源；忘记vis[v] = true有 72.09% 直接死循环，不是答案错；P1330 若把”逐连通块取较小色集”写成”全局取较小色集”，在非连通图上错 10.67%；König 定理”最小点覆盖 = 最大匹配”与”最大独立集 = $n -$ 最大匹配”在 4 万组随机二分图上零违反。文中所有代码经g++ -O2 -std=c++14 -Wall编译运行，P3386 与洛谷官方样例核对通过。前置知识：第 01 讲（存图）、第 02 讲（DFS/BFS 与
vis的意义——本讲的vis是另一个vis，第 7.2 节会专门辨析）。第 5 节要回收第 09 讲 5.3 节埋的 P1525 伏笔，没学过并查集也不影响读。不需要第 13、14 讲的dfn/low。适合对象：第 2、3、4 节标 J⭐（染色法判定 CSP-J 复赛已出现过，必须能默写）；第 5～9 节标 S；第 8.3 节标 S⭐。
P1330 封锁阳光大学：校园是一张 $N$ 个点 $M$ 条边的无向图。每只河蟹占一个点，占了这个点就封锁了与它相连的所有边。要求封锁所有边，且不能有两只河蟹占相邻的两个点。求最少需要多少只河蟹；做不到输出
Impossible。
先把条件翻译一下。设放河蟹的点集为 $S$：
一个集合既是点覆盖又是独立集，这是很强的要求。把它反过来看：每条边恰好一个端点在 $S$ 里（至少一个来自覆盖，至多一个来自独立）。也就是说，把 $S$ 染黑、$V \setminus S$ 染白，每条边的两端一黑一白。
这正是二分图的定义。于是这道题变成了：
这张图是不是二分图？如果是，黑白两色里选点数少的那一边。
暴力枚举 $2^N$ 种黑白方案在 $N \le 10^4$ 下毫无希望，但染色只要一遍 BFS。难点不在算法，在这个”每条边恰好一个端点”的翻译——以及一个几乎人人都会踩的坑（第 4.2 节）。
二分图（bipartite graph）：能把点集 $V$ 划分成两个不相交的子集 $X$ 和 $Y$，使得每条边的两个端点分属 $X$ 和 $Y$。等价地说，能用两种颜色给点染色，使每条边两端异色。
注意三件事：