GESP 题解库 / 7 级题解 / [GESP202403 七级] 交流问题 · 第 18 / 24 题
GESP202403 七级 · P10378 · 中等

交流问题

图一定被约束成二分图,求"B 校人数"的最小值与最大值。

📊
n ≤ 10⁵, m ≤ 2 × 10⁵
数据规模
🔢
int
数值类型
⚡
O(n + m)
时间复杂度
🎯
二分图染色 + 两侧规模统计
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

来自两所学校 A、B 的 n 名同学(编号 1 … n)聚在一起交流,共进行了 m 次交流,第 i 次交流在编号 uᵢ 与 vᵢ 的同学之间进行,他们因此成为了朋友。

由于目的是促进两校友谊,只有不同学校的同学之间会交流,同校同学并不会互相交流。

作为 A 校顾问,你希望求出 B 校至少有几名同学、至多有几名同学。输出一行两个整数,用一个空格隔开。

💡
人话翻译:把同学看成点、每次交流看成一条无向边。题目说"交流只发生在不同学校之间",也就是每条边的两个端点必须分属不同学校。
这正是二分图的定义!(A 校全染白、B 校全染黑,每条边恰好跨两种颜色。)
于是每个连通块被边"逼"成两边:一边给 A、一边给 B,但哪边给谁可以二选一。若这个块两侧大小是 s₁、s₂,它对 B 校人数的贡献要么 s₁、要么 s₂。
把所有块的"较小侧"加起来就是最小值,把"较大侧"加起来就是最大值;完全没有交流的孤立同学可以任意归校。

🔍 关键词提取

二分图染色判定连通块分解最小值与最大值孤立点

已知条件

项目说明
输入第一行 n, m;随后 m 行每行两个整数 uᵢ, vᵢ
输出两个整数:B 校人数的最小值、最大值
数据范围1 ≤ n ≤ 10⁵,1 ≤ m ≤ 2 × 10⁵
合法性保证输入一定合法:每条边的两端必然属于不同学校
隐含结论因此这张图一定是二分图,不会出现奇环

需要解决的问题

02
思维导图
整理解题思路的全貌
🎨 二分染色:两侧规模决定贡献
🧠 建模
同学 = 点,交流 = 边
边两端必须异校 → 图是二分图
每个连通块两侧大小 s₁, s₂
该块对 B 校的贡献只能是 s₁ 或 s₂
🔁 染色流程
遍历每个未染色的点
用栈迭代,交替染 0 / 1
同时统计两侧点数
(本题保证无冲突)
🧮 答案合并
非孤立块:最小值加 min(s₁,s₂),最大值加 max(s₁,s₂)
孤立点:天然是 (1, 0),最小加 0、最大加 1
所有块互相独立,可以放心累加
⚠️ 易错点
漏掉孤立点(最大值会偏小)
只处理了一个连通块
递归 DFS 在 10⁵ 长的链上爆栈
输出顺序写反(要求先最小后最大)
03
样例手算推导
两组样例的完整推演

🧮 样例 1:n = 4, m = 3,交流 1-2, 2-3, 4-2,答案 1 3

四个点全在同一个连通块里。从 2 号开始染色:

步骤操作染色结果
起点2 号染成 0{2} = 0 号色
第 1 轮2 号的邻居 1、3、4 全染成 1{1, 3, 4} = 1 号色
第 2 轮1、3、4 的邻居只有 2 号,已经染过,跳过不变
1
数一数两侧各有多少人

0 号色:2 号,共 1 人

1 号色:1、3、4 号,共 3 人

所以 s₁ = 1,s₂ = 3

B 校人数要么是 1、要么是 3

2
两种方案分别是什么?

方案甲:0 号色给 B 校 → B 校 = {2},1 人

方案乙:1 号色给 B 校 → B 校 = {1,3,4},3 人

题目问最少和最多,所以是 1 和 3

✅ 输出 1 3

3
样例里没有孤立点,注意别漏了

4 个点全都出现在边里

如果存在完全没有交流的同学,它会让最大值再加 1

本例暂无孤立点

min(1, 3) = 1,max(1, 3) = 3 → 答案 1 3 ✓

🧮 样例 2:n = 7, m = 5,答案 2 5

这张图有两个连通块:{1, 2, 3, 4} 和 {5, 6, 7}。分别染色后各自算出贡献,再相加。

连通块染色结果两侧大小对最小值的贡献对最大值的贡献
{1, 2, 3, 4}2 号 = 0 号色;1、3、4 号 = 1 号色1 与 313
{5, 6, 7}6 号 = 0 号色;5、7 号 = 1 号色1 与 212
合计——1 + 1 = 23 + 2 = 5
1
为什么两块可以独立累加?

两个连通块之间没有任何边

它们之间不存在"必须异校"的约束

所以各自选各自的方案,互不影响

最小值把每块的较小侧相加,最大值把每块的较大侧相加

✅ 最小值 2,最大值 5

2
用"翻色"复述一遍

第一块:B 校取 {2}(1 人)或 {1,3,4}(3 人)

第二块:B 校取 {6}(1 人)或 {5,7}(2 人)

组合起来:最小 1 + 1 = 2,最大 3 + 2 = 5

✅ 输出 2 5

🔑
两条关键的"独立性":① 每个连通块内部只有两种方案(整块翻色);② 不同连通块之间完全没有约束。
所以要最小化总和,就在每块里挑较小的那一侧;要最大化总和,就在每块里挑较大的那一侧。这是一个"每块独立二选一"的极值问题。

🧮 孤立点的作用:最小 0,最大 1

如果某位同学一次交流都没参加过(例如 n = 5, m = 2,边只有 1-2 和 3-4),那 5 号同学就是孤立点。

部分两侧大小最小贡献最大贡献
连通块 {1, 2}1 与 111
连通块 {3, 4}1 与 111
孤立点 {5}1 与 001
合计—23
⚠️
孤立点是最容易漏掉的地方:在染色流程里它会被单独处理成一个块,0 号色那一侧有 1 个人、1 号色那一侧有 0 个人,于是 min(1, 0) = 0、max(1, 0) = 1,公式天然正确。
但如果你的实现只遍历"出现在边里的点",就会把孤立点整块丢掉,最大值偏小、直接 WA。
正确做法是从 1 号到 n 号逐个检查有没有染过色。
04
解法对比
二分染色 vs 并查集(带权/种类)

⚔️ 解法对比

🟢 二分图染色 + 逐块统计(推荐) 推荐

对每个连通块做交替染色,数出两侧人数,最小值加 min、最大值加 max

  • 时间 O(n + m)
  • 只需邻接表与一个颜色数组
  • 代码约 35 行
  • 与"二分图"的定义直接对应,最好解释
💡
为什么每块恰好两种方案:连通块内任意两点的相对颜色由路径长度的奇偶决定,所以只要固定一个点的颜色,整块颜色就唯一确定;而"全部取反"显然还是合法染色。
因此每块的贡献就是"较小侧"或"较大侧"二选一。

🟠 并查集(种类/带权并查集)

维护每个点与代表元的"同色/异色"关系,最后按集合统计

  • 时间 O((n + m) α)
  • 不用建邻接表
  • 代码约 45 行
  • 偏移量/取反关系容易写错
⚠️
能用但不划算:带权并查集要额外维护"与父节点的关系",计数时还要按代表元分组,再分别统计两侧 —— 相比 BFS/DFS 染色,多绕了一层,出错的点更多。

📈 性能对比

方案复杂度代码量
二分图染色 + 逐块统计O(n + m)约 35 行
并查集(种类/带权)O((n + m) α)约 45 行,偏移量易错
枚举 2ⁿ 种归属O(2ⁿ · m)❌ n = 10⁵ 完全不可行
05
算法流程图
染色分块 + 两侧规模累加
开始读入 n, m 与所有交流,建立邻接表还有未染色的同学吗?(外层循环从 1 号扫到 n 号)取一个未染色点作起点,用栈迭代染色(起点染 0)扩展时邻居染相反色,同时把两侧人数累加进 s₁、s₂这个连通块大小为 1 吗?是 ✓孤立点:最小值加 0,最大值加 1否 ✗最小值加 min(s₁, s₂),最大值加 max(s₁, s₂)把这一块的贡献累加进 minAns 与 maxAns输出 minAns 与 maxAns(先最小后最大)回去处理下一个连通块
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🎨 B 校人数的取值范围

第一行 n m,随后 m 行每行一条交流(u v)。程序逐块染色统计两侧人数,给出最小值与最大值,并在 n ≤ 16 时用暴力枚举做对照。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(二分染色 + 两侧统计)

#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;
}
🔑
孤立点为什么不需要特判?孤立点自己成为一个大小为 1 的连通块:起点染成 0,于是 s1 = 1、s2 = 0,min(1, 0) = 0、max(1, 0) = 1。
这正是我们要的贡献!所以只要外层循环"从 1 号扫到 n 号",孤立点就会被自动处理。
反过来说,如果你只遍历"边里出现过的点",这些点就会被整块漏掉,最大值必然偏小。

📖 关键几行怎么看

代码作用为什么这样写
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);输出先最小、后最大,顺序不能反
⚠️
五个坑:① 只处理"出现在边里的点",漏掉孤立点(最大值偏小);② 染色时忘了把起点也计数进 s₁;③ 用递归 DFS,遇到 10⁵ 长的链爆栈;④ 最小值/最大值累加时把 min 和 max 写反;⑤ 输出顺序颠倒(题目要求"至少 至多",即先最小后最大)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4 3
1 2
2 3
4 2
1 3题面样例 1:一个连通块,两侧 1 与 3
7 5
1 2
2 3
4 2
5 6
6 7
2 5题面样例 2:两块分别贡献 (1,3) 与 (1,2)
2 1
1 2
1 1一条边:两人必在不同学校,B 校恰好 1 人
3 2
1 2
2 3
1 2三点链:两侧是 {2} 与 {1,3},最小 1、最大 2
4 2
1 2
3 4
2 2两条独立边:每块只能出 1 人,最小值也是 2
5 2
1 2
3 4
2 3两条边 + 一个孤立点:孤立点让最大值加 1
5 4
1 2
1 3
1 4
1 5
1 4星形图:中心一侧 1 人、叶子一侧 4 人
✅
自查清单:① 从 1 号扫到 n 号了吗(含孤立点)?② 每块的两侧人数都统计了吗?③ min 和 max 没写反吧?④ 拿"两条边 + 一个孤立点"这组数据验证过最大值是 3 吗?

🚨 易错点清单

⚠️
漏掉孤立点:孤立点对最小值贡献 0、对最大值贡献 1;只遍历边上的点会让最大值偏小。
⚠️
只处理一个连通块:图可能是若干互不相连的块,块与块之间没有约束,必须逐块累加。
⚠️
最小/最大写反:每块对 B 校的贡献是"较小侧或较大侧"二选一,最小值配 min,最大值配 max。
⚠️
输出顺序弄反:题目要求先输出最小值,再输出最大值。
⚠️
递归 DFS 爆栈:n = 10⁵ 的链要用显式栈迭代染色。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n + m)
空间复杂度
O(n + m)
n 最大
10⁵
m 最大
2 × 10⁵

时间怎么算的?

空间都用在哪?

邻接表占用 O(n + m);另外只有一个长度 n + 1 的颜色数组和染色用的显式栈。

✅ 线性扫描,毫秒级完成。本题的难点完全在"把题目翻译成二分图"这一步,代码本身只是模板级的染色与计数。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// ---- 二分图染色模板(栈迭代,防爆栈)----
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图论里"无约束变量"的通用处理
🌟
思考题:如果题目改成"求 A 校人数的最大值",答案和现在有什么关系?(提示:A 校人数 + B 校人数 = n,所以"B 校最小"对应"A 校最大",反过来也成立。
再想一步:如果题目不再保证输入合法,而是可能出现"同校同学也交流"的数据,你要怎么判断并输出无解?答案是在染色时检测 col[w] == col[u] 的冲突边——那正是"图不是二分图"的判据。)