企业官网建设流程全解析

河北手机网站制作公司,ip地址直接访问网站,angularjs 做团购网站,游戏网站排行榜前十名信奥赛C提高组csp-s之并查集#xff08;案例实践#xff09;3 题目描述 现在有 n n n 个人#xff0c;他们之间有两种关系#xff1a;朋友和敌人。我们知道#xff1a; 一个人的朋友的朋友是朋友一个人的敌人的敌人是朋友 现在要对这些人进行组团。两个人在一个团体内…信奥赛C提高组csp-s之并查集案例实践3题目描述现在有n nn个人他们之间有两种关系朋友和敌人。我们知道一个人的朋友的朋友是朋友一个人的敌人的敌人是朋友现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。输入格式第一行输入一个整数n nn代表人数。第二行输入一个整数m mm表示接下来要列出m mm个关系。接下来m mm行每行一个字符o p t optopt和两个整数p , q p,qp,q分别代表关系朋友或敌人有关系的两个人之中的第一个人和第二个人。其中o p t optopt有两种可能如果o p t optopt为F则表明p pp和q qq是朋友。如果o p t optopt为E则表明p pp和q qq是敌人。输出格式一行一个整数代表最多的团体数。输入输出样例 #1输入 #16 4 E 1 4 F 3 5 F 4 6 E 1 2输出 #13说明/提示对于100 % 100\%100%的数据2 ≤ n ≤ 1000 2 \le n \le 10002≤n≤10001 ≤ m ≤ 5000 1 \le m \le 50001≤m≤50001 ≤ p , q ≤ n 1 \le p,q \le n1≤p,q≤n。代码实现#includebits/stdc.husingnamespacestd;intn,m;intfa[2010];// 并查集数组大小为2n用于处理朋友和敌人关系// 查找操作找到x的根节点并进行路径压缩intfind(intx){if(fa[x]!x)fa[x]find(fa[x]);returnfa[x];}// 合并操作将x和y所在的集合合并voidunionSet(intx,inty){introotxfind(x);introotyfind(y);if(rootxrooty)return;// 如果已经在同一集合直接返回fa[rooty]rootx;// 合并集合}intmain(){cinnm;// 初始化并查集扩展i的虚拟结点in// i和in是敌对关系for(inti1;i2*n;i){fa[i]i;}charc;intp,q;for(inti1;im;i){cincpq;if(cF){// 朋友关系直接合并unionSet(p,q);}else{// 敌人关系// 将p与qn合并p与q的敌人是朋友// 将q与pn合并q与p的敌人是朋友// 这样实现了敌人的敌人是朋友的关系unionSet(p,qn);unionSet(q,pn);}}// 统计团体数量只检查前n个节点原始节点intcnt0;for(inti1;in;i){if(fa[i]i)cnt;// 根节点数量即为团体数量}coutcnt;return0;}功能分析核心思路朋友关系处理直接合并两个节点敌人关系处理使用反集技巧如果p和q是敌人那么p与q的敌人是朋友 → 合并p和qnq与p的敌人是朋友 → 合并q和pn算法原理使用扩展的并查集大小为2n前n个节点(1~n)表示原始人物后n个节点(n1~2n)表示敌人的敌人关系当两个人是敌人时通过合并到对方的反集节点间接实现了敌人的敌人是朋友的传递性关键特性传递性朋友的朋友是朋友敌人的敌人是朋友对称性如果p是q的敌人那么q也是p的敌人反集技巧通过创建虚拟节点来处理复杂的敌人关系各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}一、CSP信奥赛C通关学习视频课C语法基础C语法进阶C算法C数据结构CSP信奥赛数学CSP信奥赛STL二、CSP信奥赛C竞赛拿奖视频课信奥赛csp-j初赛高频考点解析CSP信奥赛C复赛集训课12大高频考点专题集训三、csp高频考点知识详解及案例实践CSP信奥赛C之动态规划CSP信奥赛C之标准模板库STL信奥赛C提高组csp-s知识详解及案例实践四、考级、竞赛刷题题单及题解GESP C考级真题题解CSP信奥赛C初赛及复赛高频考点真题解析CSP信奥赛C一等奖通关刷题题单及题解详细内容1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}