反集的反集不是朋友。。。要是把他们合并便多了1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38//并查集+反集的思想
#include<cstdio>
#include<iostream>
using namespace std;
int n,m;
int flag;
int flag1[9999];
int f[2500];
int find(int x)
{
if(f[x]!=x)
f[x]=find(f[x]);
return f[x];
}//找祖先+路径压缩
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n*2;i++)//到2n 反集
f[i]=i; //自己叫自己爸爸
for(int i=1;i<=m;i++)
{
char t;int x,y;
cin>>t>>x>>y;
if(t=='F') f[find(x)]=find(y);//朋友直接合并
if(t=='E')
{
f[find(x+n)]=find(y);//是敌人
f[find(y+n)]=find(x);//把反集合并
}
}
int s=0;
for(int i=1;i<=n;i++)
if(f[i]==i) s++;//找有多少祖先，就是有多少团伙
printf("%d",s);
return 0;
}