1 二分图
给定无向图
两侧内部都没有边,人数不必相等,也允许某一侧为空。把
图中两种画法的点和边完全相同。二分图取决于连接关系,画图时点的位置、边是否交叉,都不影响判定;线段交叉处没有标记顶点,就不产生新的顶点。
2 黑白染色
从一个未染色的点开始,把它染成黑色。它的邻点必须是白色,邻点的邻点又必须是黑色。沿边不断传播,就能确定整个连通块的颜色。
起点选择黑色或白色都可以。将一个连通块的全部颜色交换,每条边仍然异色。因此,任意指定起点颜色,不会错失原本存在的划分;后面的染色由边强制决定,无须回溯尝试。
使用 广度优先搜索(BFS):从迷宫到最少步数 实现这一传播过程。令 color[u] 为
| 邻点情况 | 处理 |
|---|---|
令 color[v] = 3 - color[u],再入队 |
|
| 当前边合法,继续检查 | |
| 两端必须异色却被强制成同色,判定失败 |
无须单独使用 visited 数组,颜色同时记录了是否已经发现该点。染色应在入队前完成,保证每个点最多入队一次。
非连通图需要从每个未染色点重新开始。整张图能二染色,当且仅当每个连通块都能二染色;不同块之间没有边,可以独立决定颜色。
3 奇环
环的长度是其中的边数。长度为奇数的环称为奇环,长度为偶数的环称为偶环。
无向图是二分图,当且仅当它不含奇环。
3.1 二分图不含奇环
沿环每走过一条边,颜色就改变一次。回到起点时必须恢复原色,因此经过的边数只能为偶数。若环长为奇数,最后一条边必然连接两个同色点,与二分图定义矛盾。
3.2 没有奇环就能二染色
对一个连通块执行前面的染色。每个点首次被发现时,记录发现它的那条边,这些边构成一棵以起点为根的搜索树。树上每经过一条边,颜色改变一次,所以颜色由树上深度的奇偶性确定。
假设检查某条边
这个长度是偶数。树上这条简单路径再加上冲突边
这里先去掉了两条根路径的公共前缀,不能把它们不加处理地拼接并直接称为简单环。上述
所以,没有奇环时,染色不会发生冲突。全部染色完成后,每条边两端异色,两类颜色就构成了二分划分。
允许自环时,自环就是长度为
4 代码实现
输入 Yes,否则输出 No。代码按
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 5;
int n, m;
vector<int> g[maxn];
int color[maxn], q[maxn]; // 0:未染色;1、2:两种颜色
bool bfs(int s) {
int head = 0, tail = 0;
color[s] = 1;
q[tail++] = s;
while (head < tail) {
int u = q[head++];
for (int v : g[u]) {
if (color[v] == 0) {
color[v] = 3 - color[u]; // 入队前染色,避免重复入队
q[tail++] = v;
} else if (color[v] == color[u]) {
return false; // 同一条边的两端被强制成同色
}
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n >> m)) return 0;
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int u = 1; u <= n; ++u) {
// 每个尚未染色的点代表一个新的连通块,孤立点也会被处理。
if (color[u] == 0 && !bfs(u)) {
cout << "No\n";
return 0;
}
}
cout << "Yes\n";
return 0;
}
判定成功后,color[u] == 1 与 color[u] == 2 的点分别组成两侧。每个连通块起点都染为
每个点最多入队一次,每条无向边按两个方向各检查一次,时间复杂度为
例如边集为 Yes;再加入 No。
| 边界情况 | 结果与处理 |
|---|---|
| 没有边,只有孤立点 | 可以二染色,孤立点可以任意分组 |
| 某个连通块包含奇环 | 整张图都不是二分图,不能只从点 |
| 同一条边输入多次 | 不影响结果,无须去重 |
| 存在自环 |
检查时两端就是同一个点,立即产生同色冲突 |
5 封锁阳光大学
选择一些点,使每条道路都至少有一个端点被选,同时相邻的两个点不能同时被选。求最少选择多少点,无解输出 Impossible。
对于任意一条边:两个端点都不选,无法封锁;两个端点都选,又会冲突。因此,要求等价于:每条边恰好选择一个端点。
把“选中”与“未选中”看成两种颜色,问题便转成二分图染色。若有同色冲突,就不存在合法方案。
对一个连通块,一旦决定某个点选不选,其他点便沿边被全部确定。因此,一个可以二染色的连通块只有两种选择:全部选颜色
BFS 时统计当前块的两类人数
先逐块取较小值,再求和。 例如两颗三叶星,边分别为
| 连通块 | 颜色 |
颜色 |
最少选择 |
|---|---|---|---|
| 第一块 | |||
| 第二块 |
选中两个中心
孤立点所在块的两类人数为
应用只在染色时增加人数统计,时间复杂度仍为
完整题解:pcs2:封锁阳光大学。逐条加入同类、异类约束的维护方法,可继续阅读 种类并查集。
6 相关题解
暂无相关题解