注册一个网站流程网页微信版官方下载
张小明 2026/1/9 4:06:43
注册一个网站流程,网页微信版官方下载,网站建设 荆州,网站首页psd下载欢迎大家订阅我的专栏#xff1a;算法题解#xff1a;C与Python实现#xff01; 本专栏旨在帮助大家从基础到进阶 #xff0c;逐步提升编程能力#xff0c;助力信息学竞赛备战#xff01;
专栏特色 1.经典算法练习#xff1a;根据信息学竞赛大纲#xff0c;精心挑选…欢迎大家订阅我的专栏算法题解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#【代码详解】#includebits/stdc.husingnamespacestd;constintN1e55;// 最大节点数intn,m,s,t;// n: 节点数, m: 边数, s,t: 边的两个端点intans1,ans2;// ans1: 最小染色数, ans2: 最大染色数intnum[3];// num[1]: 颜色1的节点数, num[2]: 颜色2的节点数intcol[N];// 每个节点的颜色0表示未染色vectorinte[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(){// 输入节点数和边数cinnm;// 输入边构建无向图for(inti1;im;i){cinst;e[s].push_back(t);e[t].push_back(s);}// 遍历所有节点for(inti1;in;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的较大值ans1min(num[1],num[2]);ans2max(num[1],num[2]);}}// 输出结果coutans1 ans2endl;return0;}【运行结果】4 3 1 2 2 3 4 2 1 3