文章目录
题目描述
给定 nnn 个人，他们之间有两个种关系，朋友与敌对。可以肯定的是：
与我的朋友是朋友的人是我的朋友
与我敌对的人有敌对关系的人是我的朋友
现在这 nnn 个人进行组团，两个人在一个团队内当且仅当他们是朋友。
求最多的团体数。 输入格式
第一行一个整数 nnn 代表人数。 第二行一个整数 mmm 代表每个人之间的关系。 接下来 mmm 行每行一个字符 optoptopt 与两个整数 p,qp,qp,q
如果 optoptopt 为 F 代表 ppp 与 qqq 为朋友。
如果 optoptopt 为 E 代表 ppp 与 qqq 为敌人。
输出格式
一行一个整数代表最多的团体数。 输入输出样例 输入 #1
6 4 E 1 4 F 3 5 F 4 6 E 1 2
输出 #1
3
说明/提示
对于 10000% 的数据，2≤n≤10002 \le n \le 10002≤n≤1000，1≤m≤50001 \le m \le 50001≤m≤5000，1≤p,q≤n1 \le p,q \le n1≤p,q≤n。
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000;
int n,m,ans=0;
int fa[maxn],g[maxn],s[maxn]={0};
void init(){
for(int i=1;i<=n;i++){
fa[i]=i;
}
}
int get(int x){
while(fa[x]!=x){
x=fa[x];
}
return x;
}
void cmp(int x,int y){
x=get(x),y=get(y);
if(x==y)return;
fa[y]=x;
return;
}
int main(){
cin>>n>>m;
init();
int a,b;
char c;
for(int i=1;i<=m;i++){
cin>>c>>a>>b;
if(c=='F')cmp(a,b);
else{
if(g[a]==0)g[a]=get(b);
else cmp(b,g[a]);
if(g[b]==0)g[b]=get(a);
else cmp(a,g[b]);
}
}
for(int i=1;i<=n;i++){
s[get(i)]++;
}
for(int i=1;i<=n;i++){
if(s[i])ans++;
}
cout<<ans;
return 0;
}
