信奥赛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

说明/提示

对于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

算法原理

使用扩展的并查集，大小为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;}

信奥赛C++提高组csp-s之并查集（案例实践）3