题目描述
现在有 n 个人，他们之间有两种关系：朋友和敌人。我们知道：
- 一个人的朋友的朋友是朋友
- 一个人的敌人的敌人是朋友
现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。
输入格式
第一行输入一个整数 n 代表人数。
第二行输入一个整数 m 表示接下来要列出 m 个关系。
接下来 m 行，每行一个字符 opt 和两个整数 p,q，分别代表关系（朋友或敌人），有关系的两个人之中的第一个人和第二个人。其中 opt 有两种可能：
- 如果 opt 为
F，则表明 p 和 q 是朋友。- 如果 opt 为
E，则表明 p 和 q 是敌人。输出格式
一行一个整数代表最多的团体数。
输入输出样例
输入 #1复制
6 4 E 1 4 F 3 5 F 4 6 E 1 2输出 #1复制
3说明/提示
对于 100% 的数据，2≤n≤1000，1≤m≤5000，1≤p,q≤n。
#include<bits/stdc++.h> using namespace std; const int N=1010; int n,m; int fa[N*2]; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } void un(int x,int y) { fa[find(y)]=find(x); } int main() { cin>>n>>m; char ch; int p,q; for(int i=1;i<=2*n;i++) fa[i]=i; while(m--) { cin>>ch>>p>>q; if(ch=='E')//敌人 { un(p,q+n); un(q,p+n); }else{ un(p,q); } } int ret=0; for(int i=1;i<=n;i++) { if(fa[i]==i) ret++; } cout<<ret<<endl; return 0; }
