题目描述 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
分类标签
Tags
点此展开
超时代码（递归时间太长了吧大概是因为）：
（温馨贴士：递归能不用则不用）
#include<iostream>
#include<cstdio>
#define Maxn 1005 using namespace std;//(F为朋友E为敌人) int f1,f2,n,m,tot=;
int F[Maxn],e[Maxn];
bool vis[Maxn]; int find(int x)
{
return x == F[x] ? x : F[x]=find(F[x]);
} void unionn(int x,int y)
{
f1=find(x);
f2=find(y);
if(f1!=f2)
{
F[f1]=f2;
if(e[f2]!=)//合并时，若r2有敌人
{
unionn(e[f2],f1);
if(e[f1]!=)//若r1也有敌人
{
unionn(e[f1],e[f2]);//则它们的敌人是朋友
}
else e[f1]=e[f2];//否则，r2的敌人同时也是r1的敌人,即他们为朋友
}
}
} int main()
{
char p;
int x,y;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)//初始化
{
F[i]=i;
e[i]=;
}
for(int i=;i<=m;i++)
{
cin>>p>>x>>y;
if(p=='F') //if x is y's friend
{
unionn(x,y); //并在一起
}
if(p=='E') //if x is y's 敌人(英语不会哈)
{
x=find(x);
if(e[x]==)//将y作为x团伙的敌人
{
e[x]=y;
}else unionn(e[x],y);
if(e[y]==)//与之类似
{
e[y]=x;
}else unionn(e[y],x);
}
}
for(int i=;i<=n;i++)
{
if(find(i)==i) tot++;//进行统计
}
printf("%d\n",tot);
return ;
}
AC代码：
其实就是把递归的地方改掉了而已，要好好的进行理解！！！
#include<iostream>
#include<cstdio>
#define Maxn 2333 using namespace std;//(F为朋友E为敌人) int f1,f2,n,m,tot=;
int F[Maxn],e[Maxn]; int find(int x)
{
return x == F[x] ? x : F[x]=find(F[x]);
} int main()
{
char p;
int x,y;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)//初始化
{
F[i]=i;
}
for(int i=;i<=m;i++)
{
cin>>p>>x>>y;
if(p=='F') //if x is y's friend
{
f1=find(x);f2=find(y);
if(f1!=f2) F[f1]=f2; //并在一起
}
if(p=='E') //if x is y's 敌人(英语不会哈)
{
e[x] ? F[find(e[x])] = find(y) : e[x]=y;//x有敌人么？有就将y的集团与x敌人的集团并起来，没有就将y作为x的敌人
e[y] ? F[find(e[y])] = find(x) : e[y]=x;//同上
}
}
for(int i=;i<=n;i++)
{
if(find(i)==i) tot++;//进行统计
}
printf("%d\n",tot);
return ;
}