题目描述 Description
1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是：
我朋友的朋友是我的朋友；
我敌人的敌人也是我的朋友。
两个强盗是同一团伙的条件是当且仅当他们是朋友。现在给你一些关于强盗们的信息，问你最多有多少个强盗团伙。
输入描述 Input Description
输入文件gangs.in的第一行是一个整数N(2<=N<=1000)，表示强盗的个数（从1编号到N）。 第二行M(1<=M<=5000)，表示关于强盗的信息条数。 以下M行，每行可能是F p q或是E p q（1<=p q<=N），F表示p和q是朋友，E表示p和q是敌人。输入数据保证不会产生信息的矛盾。
输出描述 Output Description
输出文件gangs.out只有一行，表示最大可能的团伙数。
样例输入 Sample Input
6
4
E 1 4
F 3 5
F 4 6
E 1 2
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
2<=N<=1000
1<=M<=5000
1<=p q<=N
解析：
说实话这道题在想怎么处理敌人的敌人是朋友时我纠结了好久，但是在看了一位大牛的思路后我想通了。这道题不能想太死板，做以下几个步骤就行
1.输入时新开一个数组记录当前的敌人，如果已经记录那就可以让敌人的敌人变成朋友：比如样例中E 1 4 ，我发现这时候的e数组的1,4下标
为空，我就让e[1]=4,e[4]=1;到了E 1 2时，发现e[1]有值了，那么2和4就是朋友关系change(2,4);e[2]=1;e[1]=2;
2.做到这里时，你可能会觉得2会把4给覆盖了，但其实没有问题，e[1]这时候的值是2,而2和4已经处于一个集合里面了，就不会影响后来的分团伙
可能说的不是很清楚，咱还是看代码吧
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#define maxn 5005
using namespace std;
int f[maxn],e[maxn],vis[maxn];
int n,m,q;
void first()
{
for(int i=1;i<=n;i++)
{
f[i]=i;e[i]=0;
}
}
int find_father(int x)
{
if(f[x]==x)return x;
return find_father(f[x]);
}
void change(int a,int b)
{
int af=find_father(a),bf=find_father(b);
if(af!=bf)
{
f[max(bf,af)]=min(bf,af);//让所有的点的根都尽量偏小，是方便统一
}
}
int main()
{
scanf("%d%d",&n,&m);
first();
for(int i=1;i<=m;i++)
{
int a,b;char c;
cin>>c>>a>>b;
if(c=='F')change(a,b);
else{
if(e[a]!=0)change(e[a],b);//敌人的敌人就是朋友
if(e[b]!=0)change(e[b],a);
e[a]=b;e[b]=a;//标记敌人
}
}
for(int i=1;i<=n;i++)
{
f[i]=find_father(i);//让所有人都找到自己的集合
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(vis[find_father(i)]==0)
{
ans++;
vis[find_father(i)]=1;
}
}
printf("%d",ans);
}