你好！我是你的OI教练。很高兴能带你攻克这道 GESP 七级的题目《交流问题》。

这道题是图论中**二部图（Bipartite Graph）**应用的经典入门题。虽然题目包装成了同学交流的场景，但核心逻辑非常直观。

我们先拿出草稿纸，把题目中的逻辑画成图，你会发现这其实是一个关于“站队”的问题。

1. 读题关键词：你的“雷达”响了吗？

在读题时，请圈出以下决定解题方向的关键词：

1. “只有不同学校的同学之间会交流”：
   • 核心暗示：这是一个二部图。
   • 如果把学生看作点，交流看作边，那么整张图的所有边都连接着“A校”集合和“B校”集合。同一个集合内部没有连边。
2. “$B$ 校至少...至多...”：
   • 这提示我们需要计算某种可能性的范围。
   • 由于图可能是不连通的（分成了好几个小圈子），每个小圈子内部的 A/B 分配互不影响。
3. “$N \le 10^5, M \le 2 \times 10^5$”：
   • 数据范围较大，必须使用线性时间复杂度的算法，比如 DFS 或 BFS，复杂度 $O(N+M)$。

2. 预备知识点

要解决这道题，你需要掌握：

• 图的存储：邻接表 (vector<int> adj[])。
• 图的遍历：DFS 或 BFS（用于染色）。
• 二部图染色法：将相连的点染成不同颜色（0 和 1）。
• 连通块：图可能是不连通的，需要对每个连通分量单独处理。

3. 启发式教学：草稿纸上的推演

假设输入样例 2：

• Edges: 1-2, 2-3, 4-2, 5-6, 6-7

我们在草稿纸上画出连接关系：

连通块 1：

    1
    |
    2 -- 4
    |
    3

• 这是一个连通的整体。
• 如果我们假设 2号 是 A 校（颜色0）：
  • 那么与它相连的 1, 3, 4 必须是 B 校（颜色1）。
  • 此时：A校1人，B校3人。
• 如果我们假设 2号 是 B 校（颜色1）：
  • 那么 1, 3, 4 必须是 A 校（颜色0）。
  • 此时：B校1人，A校3人。
• 小结：在这个小圈子里，B校的人数要么是 1，要么是 3。

连通块 2：

    5 -- 6 -- 7

• 如果我们假设 6号 是 A 校（颜色0）：
  • 那么 5, 7 是 B 校（颜色1）。
  • 此时：A校1人，B校2人。
• 反之：
  • 此时：B校1人，A校2人。
• 小结：在这个小圈子里，B校的人数要么是 1，要么是 2。

全局统计： 题目问 B 校总人数的 最少 和 最多。

• 最少情况：我们在每个圈子里都让 B 校人最少。
  • 连通块1选1人，连通块2选1人 $\to$ 总共 $1+1=2$ 人。
• 最多情况：我们在每个圈子里都让 B 校人最多。
  • 连通块1选3人，连通块2选2人 $\to$ 总共 $3+2=5$ 人。

结论：

1. 遍历全图，找到所有的连通块。
2. 对每个连通块进行黑白染色（0/1染色），统计两种颜色的节点数量 cnt0 和 cnt1。
3. min_ans += min(cnt0, cnt1)
4. max_ans += max(cnt0, cnt1)

4. 标准代码 (NOIP C++14)

/**
 * 题目：P10378 [GESP202403 七级] 交流问题
 * 考点：图论、二部图染色、连通块、贪心
 * 时间复杂度：O(N + M)
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;

// 邻接表存图
vector<int> adj[MAXN];
// color数组：-1表示未访问，0表示A校，1表示B校
int color[MAXN];
// 统计当前连通块中两种颜色的人数
int cnt[2];

// DFS 进行二部图染色
// u: 当前节点, c: 当前节点的颜色(0或1)
void dfs(int u, int c) {
    color[u] = c;
    cnt[c]++; // 统计人数

    for (int v : adj[u]) {
        if (color[v] == -1) {
            // 如果相邻节点没访问过，染成相反颜色 (1-c)
            dfs(v, 1 - c);
        } else {
            // 如果访问过，题目保证输入合法（一定是二部图），
            // 所以这里不需要判断 color[v] == c 的冲突情况。
        }
    }
}

void solve() {
    int n, m;
    if (!(cin >> n >> m)) return;

    // 清空邻接表（多测时需要，单测是个好习惯）
    for (int i = 1; i <= n; i++) {
        adj[i].clear();
        color[i] = -1; // 初始化为未访问
    }

    // 读入边
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int min_b = 0;
    int max_b = 0;

    // 遍历所有节点，处理每个连通块
    for (int i = 1; i <= n; i++) {
        if (color[i] == -1) {
            // 发现一个新的连通块
            cnt[0] = 0; 
            cnt[1] = 0;
            
            // 从该点开始 DFS，假设它染成颜色 0
            dfs(i, 0);

            // 贪心策略：
            // 这个连通块对 B 校贡献的最少人数，是两种颜色中较少的那个
            min_b += min(cnt[0], cnt[1]);
            // 这个连通块对 B 校贡献的最多人数，是两种颜色中较多的那个
            max_b += max(cnt[0], cnt[1]);
        }
    }

    cout << min_b << " " << max_b << endl;
}

int main() {
    // IO优化
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}

5. 易错点与关键点注释

1. 孤立点处理：
   • 如果有同学一次交流都没参加（孤立点），DFS 会把这个点算作一个独立的连通块。
   • cnt[0]=1, cnt[1]=0。
   • min += 0, max += 1。这符合逻辑：他可以是 A 校（不给 B 贡献），也可以是 B 校（给 B 贡献）。
2. 输入合法性：
   • 题目保证“输入是合法的”，意味着图一定没有奇环，一定是二部图，所以我们在 DFS 时不需要写 return false 来判错。
3. 数据范围：
   • $N$ 到 $10^5$，递归深搜可能会爆栈吗？通常竞赛中栈空间够用，但如果是极其特殊的链状图，层数过深可能爆栈。C++14 在 NOIP/CSP 中通常会开大栈空间，或者可以改用 BFS（广度优先搜索）来避免爆栈风险。不过对于本题 BFS 和 DFS 均可 AC。

6. 数据生成器 (1.in - 10.in)

/**
 * P10378 数据生成器
 * 生成 1.in/1.out ~ 10.in/10.out
 */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <numeric>

using namespace std;

// ---------------- 标准题解逻辑 (用于生成 .out) ----------------
const int MAXN_SOLVE = 100005;
vector<int> adj_solve[MAXN_SOLVE];
int color_solve[MAXN_SOLVE];
int cnt_solve[2];

void dfs_solve(int u, int c) {
    color_solve[u] = c;
    cnt_solve[c]++;
    for (int v : adj_solve[u]) {
        if (color_solve[v] == -1) {
            dfs_solve(v, 1 - c);
        }
    }
}

pair<int, int> solve_std(int n, int m, const vector<pair<int, int>>& edges) {
    for (int i = 1; i <= n; i++) {
        adj_solve[i].clear();
        color_solve[i] = -1;
    }
    for (auto& e : edges) {
        adj_solve[e.first].push_back(e.second);
        adj_solve[e.second].push_back(e.first);
    }
    int min_b = 0, max_b = 0;
    for (int i = 1; i <= n; i++) {
        if (color_solve[i] == -1) {
            cnt_solve[0] = 0; cnt_solve[1] = 0;
            dfs_solve(i, 0);
            min_b += min(cnt_solve[0], cnt_solve[1]);
            max_b += max(cnt_solve[0], cnt_solve[1]);
        }
    }
    return {min_b, max_b};
}
// -------------------------------------------------------------

int randInt(int l, int r) {
    return rand() % (r - l + 1) + l;
}

void makeData(int id) {
    string inName = to_string(id) + ".in";
    string outName = to_string(id) + ".out";
    ofstream fin(inName);
    ofstream fout(outName);

    int n, m;
    // 梯度数据
    if (id <= 3) {
        n = randInt(5, 17);
        m = randInt(1, 30);
    } else if (id <= 6) {
        n = randInt(100, 500);
        m = randInt(n, 2000);
    } else {
        n = randInt(10000, 100000);
        m = randInt(n, 200000);
    }

    // 构造二部图：先给每个人预分配阵营，然后只在不同阵营间加边
    vector<int> team(n + 1);
    for (int i = 1; i <= n; i++) team[i] = randInt(0, 1);

    vector<pair<int, int>> edges;
    // 保证图不是极度稀疏，尽量生成一些边
    // 随机加边策略
    int attempts = 0;
    while (edges.size() < m && attempts < m * 5) {
        attempts++;
        int u = randInt(1, n);
        int v = randInt(1, n);
        if (u != v && team[u] != team[v]) {
            edges.push_back({u, v});
        }
    }
    m = edges.size(); // 更新实际边数

    fin << n << " " << m << endl;
    for (auto& e : edges) {
        fin << e.first << " " << e.second << endl;
    }

    pair<int, int> ans = solve_std(n, m, edges);
    fout << ans.first << " " << ans.second << endl;

    fin.close();
    fout.close();
    cout << "Generated Case " << id << " (N=" << n << ", M=" << m << ")" << endl;
}

int main() {
    srand(time(0));
    for (int i = 1; i <= 10; i++) makeData(i);
    return 0;
}