题目描述
众所周知，香港的黑社会组织猖獗，警方希望能摸清他们的内部构成情况，特派小生前往调查。经过长期的卧底，小生初步获得了一些资料：整个组织有 n 个人，任何两个认识的人不是朋友就是敌人。
而且满足：①我朋友的朋友是我的朋友；②我敌人的敌人是我的朋友。所有是朋友的人组成一个团伙。
现在，警方委派你协助调查，拥有关于这 n 个人的 m 条信息（即某两个人是朋友，或某两个人是敌人） ，请你计算出这个城市最多可能有多少个团伙。
数据范围
2≤N≤2000，1≤M≤5000。
输入输出格式
输入描述：
第一行包含一个整数 N，第二行包含一个整数 M，接下来 M 行描述 M 条信息。
内容为以下两者之一：“F x y”表示 x 与 y 是朋友；“E x y”表示 x 与 y 是敌人（1≤x≤y≤N） 。
输出描述：
包含一个整数，即可能的最大团伙数。
输入输出样例
输入样例：
6
4
E 1 4
F 3 5
F 4 6
E 1 2
输出样例：
3
思路
并查集。用1—n表示朋友，若p[0]==F，则unionn(x,y);用n+1—2*n表示敌人，若p[0]==E，则unionn(x,y+n),unionn(y,x+n)。
代码
#include<stdio.h>
#include<string.h>
int a[];
char p[];
int find(int x)
{
if(a[x]!=x)
x=find(a[x]);
return a[x];
}
void unionn(int x,int y)
{
x=find(x);
y=find(y);
a[y]=x;
}
int main()
{
int n,m,x,y,i,j,z,k=;
scanf("%d%d",&n,&m);
for(i=;i<=n*;i++)
a[i]=i;
for(i=;i<=m;i++)
{
scanf("%s%d%d",p,&x,&y);
if(p[]=='F')
unionn(x,y);
if(p[]=='E')
{
unionn(x,y+n);
unionn(y,x+n);
}
}
for(i=;i<=n;i++)
a[i]=find(i);
for(i=;i<n;i++)
for(j=;j<=n-i;j++)
if(a[j]>a[j+])
{
z=a[j];
a[j]=a[j+];
a[j+]=z;
}
for(i=;i<=n;i++)
if(a[i]!=a[i-])
k++;
printf("%d",k);
return ;
}