图一定被约束成二分图,求"B 校人数"的最小值与最大值。
来自两所学校 A、B 的 n 名同学(编号 1 … n)聚在一起交流,共进行了 m 次交流,第 i 次交流在编号 uᵢ 与 vᵢ 的同学之间进行,他们因此成为了朋友。
由于目的是促进两校友谊,只有不同学校的同学之间会交流,同校同学并不会互相交流。
作为 A 校顾问,你希望求出 B 校至少有几名同学、至多有几名同学。输出一行两个整数,用一个空格隔开。
二分图染色判定连通块分解最小值与最大值孤立点
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n, m;随后 m 行每行两个整数 uᵢ, vᵢ |
| 输出 | 两个整数:B 校人数的最小值、最大值 |
| 数据范围 | 1 ≤ n ≤ 10⁵,1 ≤ m ≤ 2 × 10⁵ |
| 合法性保证 | 输入一定合法:每条边的两端必然属于不同学校 |
| 隐含结论 | 因此这张图一定是二分图,不会出现奇环 |
四个点全在同一个连通块里。从 2 号开始染色:
| 步骤 | 操作 | 染色结果 |
|---|---|---|
| 起点 | 2 号染成 0 | {2} = 0 号色 |
| 第 1 轮 | 2 号的邻居 1、3、4 全染成 1 | {1, 3, 4} = 1 号色 |
| 第 2 轮 | 1、3、4 的邻居只有 2 号,已经染过,跳过 | 不变 |
0 号色:2 号,共 1 人
1 号色:1、3、4 号,共 3 人
所以 s₁ = 1,s₂ = 3
B 校人数要么是 1、要么是 3
方案甲:0 号色给 B 校 → B 校 = {2},1 人
方案乙:1 号色给 B 校 → B 校 = {1,3,4},3 人
题目问最少和最多,所以是 1 和 3
✅ 输出 1 3
4 个点全都出现在边里
如果存在完全没有交流的同学,它会让最大值再加 1
本例暂无孤立点
min(1, 3) = 1,max(1, 3) = 3 → 答案 1 3 ✓
这张图有两个连通块:{1, 2, 3, 4} 和 {5, 6, 7}。分别染色后各自算出贡献,再相加。
| 连通块 | 染色结果 | 两侧大小 | 对最小值的贡献 | 对最大值的贡献 |
|---|---|---|---|---|
| {1, 2, 3, 4} | 2 号 = 0 号色;1、3、4 号 = 1 号色 | 1 与 3 | 1 | 3 |
| {5, 6, 7} | 6 号 = 0 号色;5、7 号 = 1 号色 | 1 与 2 | 1 | 2 |
| 合计 | — | — | 1 + 1 = 2 | 3 + 2 = 5 |
两个连通块之间没有任何边
它们之间不存在"必须异校"的约束
所以各自选各自的方案,互不影响
最小值把每块的较小侧相加,最大值把每块的较大侧相加
✅ 最小值 2,最大值 5
第一块:B 校取 {2}(1 人)或 {1,3,4}(3 人)
第二块:B 校取 {6}(1 人)或 {5,7}(2 人)
组合起来:最小 1 + 1 = 2,最大 3 + 2 = 5
✅ 输出 2 5
如果某位同学一次交流都没参加过(例如 n = 5, m = 2,边只有 1-2 和 3-4),那 5 号同学就是孤立点。
| 部分 | 两侧大小 | 最小贡献 | 最大贡献 |
|---|---|---|---|
| 连通块 {1, 2} | 1 与 1 | 1 | 1 |
| 连通块 {3, 4} | 1 与 1 | 1 | 1 |
| 孤立点 {5} | 1 与 0 | 0 | 1 |
| 合计 | — | 2 | 3 |
对每个连通块做交替染色,数出两侧人数,最小值加 min、最大值加 max
维护每个点与代表元的"同色/异色"关系,最后按集合统计
| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 二分图染色 + 逐块统计 | O(n + m) | 约 35 行 |
| 并查集(种类/带权) | O((n + m) α) | 约 45 行,偏移量易错 |
| 枚举 2ⁿ 种归属 | O(2ⁿ · m) | ❌ n = 10⁵ 完全不可行 |
第一行 n m,随后 m 行每行一条交流(u v)。程序逐块染色统计两侧人数,给出最小值与最大值,并在 n ≤ 16 时用暴力枚举做对照。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int n, m; vector<int> g[100005]; int col[100005]; // -1 未染色;0 / 1 表示两个不同的颜色 int main() { scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int u, v; scanf("%d %d", &u, &v); g[u].push_back(v); g[v].push_back(u); } fill(col, col + n + 1, -1); long long mn = 0, mx = 0; // 累加时用 long long 更保险 for (int s = 1; s <= n; s++) { if (col[s] != -1) continue; // 已经从别的点染过这个块了 // ---- 迭代染色:同时统计两侧人数 ---- vector<int> stk; stk.push_back(s); col[s] = 0; long long s1 = 0, s2 = 0; while (!stk.empty()) { int u = stk.back(); stk.pop_back(); if (col[u] == 0) s1++; else s2++; // 记在正确的一侧 for (int w : g[u]) { if (col[w] == -1) { // 没染过:染成相反色 col[w] = col[u] ^ 1; stk.push_back(w); } // 本题保证输入合法,不会出现 col[w] == col[u] 的情况 } } mn += min(s1, s2); // 这一块给 B 校的"最少可能" mx += max(s1, s2); // 这一块给 B 校的"最多可能" } printf("%lld %lld\n", mn, mx); return 0; }
s1 = 1、s2 = 0,min(1, 0) = 0、max(1, 0) = 1。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
for (int s = 1; s <= n; s++) | 外层扫描 | 必须扫遍所有点,才能带上孤立点 |
col[w] = col[u] ^ 1; | 交替染色 | 异或 1 就是"取反",0 变 1、1 变 0 |
if (col[u] == 0) s1++; else s2++; | 两侧计数 | 注意按"弹出的那个点"的颜色计数 |
mn += min(s1, s2); | 最小值贡献 | 这一块哪一侧给 B 校都能成立,取小的 |
mx += max(s1, s2); | 最大值贡献 | 同理取大的;块与块之间互不干扰 |
printf("%lld %lld\n", mn, mx); | 输出 | 先最小、后最大,顺序不能反 |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 3 | 1 3 | 题面样例 1:一个连通块,两侧 1 与 3 |
7 5 | 2 5 | 题面样例 2:两块分别贡献 (1,3) 与 (1,2) |
2 1 | 1 1 | 一条边:两人必在不同学校,B 校恰好 1 人 |
3 2 | 1 2 | 三点链:两侧是 {2} 与 {1,3},最小 1、最大 2 |
4 2 | 2 2 | 两条独立边:每块只能出 1 人,最小值也是 2 |
5 2 | 2 3 | 两条边 + 一个孤立点:孤立点让最大值加 1 |
5 4 | 1 4 | 星形图:中心一侧 1 人、叶子一侧 4 人 |
邻接表占用 O(n + m);另外只有一个长度 n + 1 的颜色数组和染色用的显式栈。
✅ 线性扫描,毫秒级完成。本题的难点完全在"把题目翻译成二分图"这一步,代码本身只是模板级的染色与计数。
// ---- 二分图染色模板(栈迭代,防爆栈)---- fill(col, col + n + 1, -1); long long mn = 0, mx = 0; for (int s = 1; s <= n; s++) { if (col[s] != -1) continue; // 注意:必须扫遍所有点,别漏孤立点 vector<int> stk{s}; col[s] = 0; long long c[2] = {0, 0}; while (!stk.empty()) { int u = stk.back(); stk.pop_back(); c[col[u]]++; for (int w : g[u]) { if (col[w] == -1) { col[w] = col[u] ^ 1; stk.push_back(w); } else if (col[w] == col[u]) { /* 出现奇环 → 不是二分图 */ } } } mn += min(c[0], c[1]); // 每块独立二选一 mx += max(c[0], c[1]); } // ---- 孤立点自动被覆盖 ---- // 大小为 1 的连通块:c[0] = 1, c[1] = 0 // min(1, 0) = 0 → 最小值贡献 0 // max(1, 0) = 1 → 最大值贡献 1 // ---- 如果题目改成"输入可能不合法" ---- // 染色时发现 col[w] == col[u] 就说明出现了奇环, // 此时无解,直接判定"方案不存在"
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 二分图染色 | 把"异校交流"的约束变成颜色交替 | 奇环判定、冲突检测、2-SAT 的雏形 |
| 连通块分解 | 把 n 个点拆成互不干扰的若干块 | 连通块计数、缩点、强连通分量 |
| 每块独立取 min/max | 线性合成全局最值 | 背包、贪心合并、区间决策 |
| 孤立点单独消化 | 自由度最大的点,贡献 0 或 1 | 图论里"无约束变量"的通用处理 |
col[w] == col[u] 的冲突边——那正是"图不是二分图"的判据。)