欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
【题目来源】
洛谷：[P10378 GESP202403 七级] 交流问题 - 洛谷
【题目描述】
来自两所学校A AA、B BB的n nn名同学聚在一起相互交流。为了方便起见，我们把这些同学从1 11至n nn编号。他们共进行了m mm次交流，第i ii次交流中，编号为u i , v i u_i, v_iui,vi的同学相互探讨了他们感兴趣的话题，并结交成为了新的朋友。
由于这次交流会的目的是促进两校友谊，因此只有不同学校的同学之间会交流。同校同学并不会互相交流。
作为A AA校顾问，你对B BB校的规模非常感兴趣，你希望求出B BB校至少有几名同学、至多有几名同学。
【输入】
第一行两个正整数，表示同学的人数n nn、交流的次数m mm。
接下来m mm行，每行两个整数u i , v i u_i, v_iui,vi，表示一次交流。
【输出】
输出一行两个整数，用单个空格隔开，分别表示B BB校至少有几名同学、至多有几名同学。
【输入样例】
4 3 1 2 2 3 4 2【输出样例】
1 3【算法标签】
《洛谷 P10378 交流问题》 #搜索# #图论# #并查集# #图论建模# #二分图# #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;// 最大节点数intn,m,s,t;// n: 节点数, m: 边数, s,t: 边的两个端点intans1,ans2;// ans1: 最小染色数, ans2: 最大染色数intnum[3];// num[1]: 颜色1的节点数, num[2]: 颜色2的节点数intcol[N];// 每个节点的颜色，0表示未染色vector<int>e[N];// 邻接表存储图// 深度优先搜索进行二分图染色voiddfs(intu){// 遍历节点u的所有邻居节点vfor(autov:e[u]){// 如果邻居节点v还未染色if(col[v]==0){// 将v染成与u不同的颜色// 如果col[u]=1，则col[v]=2；如果col[u]=2，则col[v]=1col[v]=3-col[u];num[col[v]]++;// 对应颜色的节点数加1dfs(v);// 递归染色v的邻居}}}intmain(){// 输入节点数和边数cin>>n>>m;// 输入边，构建无向图for(inti=1;i<=m;i++){cin>>s>>t;e[s].push_back(t);e[t].push_back(s);}// 遍历所有节点for(inti=1;i<=n;i++){// 如果节点i还未染色，说明找到一个新的连通分量if(col[i]==0){// 初始化当前连通分量的颜色计数num[1]=1;// 从颜色1开始，所以num[1]=1num[2]=0;// 颜色2初始为0// 将节点i染成颜色1col[i]=1;// 从节点i开始进行DFS染色dfs(i);// 统计当前连通分量的结果// ans1: 最小化颜色1和颜色2的较小值// ans2: 最大化颜色1和颜色2的较大值ans1+=min(num[1],num[2]);ans2+=max(num[1],num[2]);}}// 输出结果cout<<ans1<<" "<<ans2<<endl;return0;}【运行结果】
4 3 1 2 2 3 4 2 1 3
