大家好，我是энтджей，今天是我2026年第十三次正式发题解！

2026年发布的题解！

能不能点个赞

---

首先简化题意：

• 这道题个人认为有一点点抽象，你可以把所有人看做一个图，然后要求相连通的结点的学校不同，转换一下，就是让你染色，然后求相同颜色的最少和最多的个数（感觉讲得好不通顺）

然后就是写代码

• 处理输入（read）：

  • 正常输入

• 核心部分（process）：

  • 寻找没有被染色的结点进行联通块染色处理（bfs）

  • 处理联通块（bfs）;

    • 用最最最最常规的方式，定义queue，遍历所有与他相邻但未被染色的结点进行不同颜色的染色，并进行变量的增减

• 最后输出（write）：

  • 输出最少和最多相同颜色结点的个数

完整代码：

#include<bits/stdc++.h>
#define int long long  
using namespace std;
const int N = 1e5 + 10;
int n,m;
int maxn = 0,minn = 0;
vector<int> ve[N];
bool vis[N];
int color[N];
void bfs(int id, int& cnt0, int& cnt1){
    queue<int> q;
    q.push(id);
    vis[id] = true;
    color[id] = 0;
    cnt0 = 1,cnt1 = 0;
    while(!q.empty()){ //遍历这个联通块的所有结点
        int u = q.front();
        q.pop();
        for( auto v : ve[u]) {
            if(!vis[v]){
                vis[v] = true;
                color[v] = (color[u] == 1) ? 0 : 1; //反向染色，用^1也可以
                cnt0 += (color[v] == 0) ? 1 : 0; //变量增减
                cnt1 += (color[v] == 1) ? 1 : 0; //变量增减
                q.push(v);
            }
        }
    }
}
void init() { //其实没有什么用
    memset(vis, false, sizeof vis);
}
void read() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u,v;
        cin >> u >> v;
        ve[u].push_back(v),ve[v].push_back(u);
    }
}
void process() {
    init();
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            int cnt0 = 0,cnt1 = 0;
            bfs(i, cnt0, cnt1);
            minn += min(cnt0, cnt1); //最少的人数变量增加
            maxn += max(cnt0, cnt1); //最多的人数变量增加
        }
    }
}
void write() {
    cout << minn << " " << maxn;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    read();
    process();
    write();
    return 0;
}

---

🎉完结撒花🎉