信奥赛C++提高组csp-s之并查集（案例实践）3
信奥赛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
输入 #1
6 4 E 1 4 F 3 5 F 4 6 E 1 2输出 #1
3说明/提示
对于100 % 100\%100%的数据，2 ≤ n ≤ 1000 2 \le n \le 10002≤n≤1000，1 ≤ m ≤ 5000 1 \le m \le 50001≤m≤5000，1 ≤ p , q ≤ n 1 \le p,q \le n1≤p,q≤n。
代码实现
#include<bits/stdc++.h>usingnamespacestd;intn,m;intfa[2010];// 并查集数组，大小为2n，用于处理朋友和敌人关系// 查找操作：找到x的根节点，并进行路径压缩intfind(intx){if(fa[x]!=x)fa[x]=find(fa[x]);returnfa[x];}// 合并操作：将x和y所在的集合合并voidunionSet(intx,inty){introotx=find(x);introoty=find(y);if(rootx==rooty)return;// 如果已经在同一集合，直接返回fa[rooty]=rootx;// 合并集合}intmain(){cin>>n>>m;// 初始化并查集，扩展i的虚拟结点i+n// i和i+n是敌对关系for(inti=1;i<=2*n;i++){fa[i]=i;}charc;intp,q;for(inti=1;i<=m;i++){cin>>c>>p>>q;if(c=='F'){// 朋友关系：直接合并unionSet(p,q);}else{// 敌人关系：// 将p与q+n合并（p与q的敌人是朋友）// 将q与p+n合并（q与p的敌人是朋友）// 这样实现了"敌人的敌人是朋友"的关系unionSet(p,q+n);unionSet(q,p+n);}}// 统计团体数量：只检查前n个节点（原始节点）intcnt=0;for(inti=1;i<=n;i++){if(fa[i]==i)cnt++;// 根节点数量即为团体数量}cout<<cnt;return0;}功能分析
核心思路
- 朋友关系处理：直接合并两个节点
- 敌人关系处理：使用"反集"技巧
- 如果p和q是敌人，那么：
- p与q的敌人是朋友 → 合并p和q+n
- q与p的敌人是朋友 → 合并q和p+n
- 如果p和q是敌人，那么：
算法原理
- 使用扩展的并查集，大小为2n
- 前n个节点(1~n)表示原始人物
- 后n个节点(n+1~2n)表示"敌人的敌人"关系
- 当两个人是敌人时，通过合并到对方的反集节点，间接实现了"敌人的敌人是朋友"的传递性
关键特性
- 传递性：朋友的朋友是朋友，敌人的敌人是朋友
- 对称性：如果p是q的敌人，那么q也是p的敌人
- 反集技巧：通过创建虚拟节点来处理复杂的敌人关系
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;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++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
4、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 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}