2024年3月GESP真题及题解(C++七级): 交流问题-编程实验室

2024年3月GESP真题及题解(C++七级): 交流问题

题目描述

来自两所学校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校至少有几名同学、至多有几名同学。

输入输出样例 1

输入 1

4 3 1 2 2 3 4 2

输出 1

1 3

输入输出样例 2

输入 2

7 5 1 2 2 3 4 2 5 6 6 7

输出 2

2 5

说明/提示

数据规模与约定

对30 % 30\%30%的数据，保证n ≤ 17 n \leq 17n≤17，m ≤ 50 m \leq 50m≤50。
对60 % 60\%60%的数据，保证n ≤ 500 n \leq 500n≤500，m ≤ 2000 m \leq 2000m≤2000。
对全部的测试数据，保证1 ≤ u i , v i ≤ n ≤ 10 5 1 \leq u_i, v_i \leq n \leq 10^51≤ui,vi≤n≤105，1 ≤ m ≤ 2 × 10 5 1 \leq m \leq 2\times 10^51≤m≤2×105，输入是合法的，即交流一定是跨校开展的。

思路分析

问题可转化为：给定一个无向图，每条边连接的两个顶点必须属于不同的集合（A校和B校）。求在满足所有边约束的前提下，B校顶点数量的最小可能值和最大可能值。

由于只有两个学校，图必须是二分图（题目保证输入合法）。对于每个连通分量，进行二分图染色后，得到两种颜色的顶点数。对于该分量，有两种分配方式（将颜色0分给B校或颜色1分给B校），因此B校人数可以是该分量中颜色0的个数或颜色1的个数。

对于整个图，每个连通分量的选择独立，因此B校总人数的最小值就是所有连通分量中较少颜色数之和，最大值就是所有连通分量中较多颜色数之和。

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintN=100005;vector<int>g[N];// 邻接表intcol[N];// 颜色，0或1，-1表示未染色intmain(){ios::sync_with_stdio(false);cin.tie(0);intn,m;cin>>n>>m;// 建图for(inti=0;i<m;++i){intu,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}memset(col,-1,sizeof(col));longlongmn=0,mx=0;// B校人数的最小值和最大值// 遍历所有连通分量for(inti=1;i<=n;++i){if(col[i]!=-1)continue;// 已染色// BFS染色queue<int>q;q.push(i);col[i]=0;// 起始点染0intcnt0=0,cnt1=0;// 统计当前连通分量中两种颜色的数量while(!q.empty()){intu=q.front();q.pop();if(col[u]==0)cnt0++;elsecnt1++;for(intv:g[u]){if(col[v]==-1){col[v]=col[u]^1;// 染相反颜色q.push(v);}// 题目保证输入合法，无需检查冲突}}// 更新答案mn+=min(cnt0,cnt1);mx+=max(cnt0,cnt1);}cout<<mn<<" "<<mx<<"\n";return0;}

功能分析

图存储：使用邻接表存储无向图，空间复杂度 O(n+m)。
二分图染色：使用 BFS 对每个连通分量进行染色，保证每条边两端颜色不同。时间复杂度 O(n+m)。
统计与计算：对每个连通分量统计两种颜色的节点数，分别累加较小值得到 B 校最少人数，累加较大值得到 B 校最多人数。
注意事项：
- 由于图可能不连通，需要遍历所有节点确保每个连通分量都被处理。
- 使用 BFS 避免递归深度过大。
- 题目保证输入合法（图是二分图），因此无需检查染色冲突。
- 使用 long long 防止累加时溢出（n最大1e5，但多个分量累加可能超过int范围）。
复杂度分析：

时间复杂度：O(n + m)，每个节点和每条边各访问一次。
空间复杂度：O(n + m)，用于存储图和队列。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

2024年3月GESP真题及题解(C++七级): 交流问题