P1892 [BOI2003]团伙
题目描述
1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是：
我朋友的朋友是我的朋友；
我敌人的敌人也是我的朋友。
两个强盗是同一团伙的条件是当且仅当他们是朋友。现在给你一些关于强盗们的信息，问你最多有多少个强盗团伙。
输入格式：
输入文件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是敌人。输入数据保证不会产生信息的矛盾。
输出格式：
输出文件gangs.out只有一行，表示最大可能的团伙数。
输入样例#1：
6 4 E 1 4 F 3 5 F 4 6 E 1 2
输出样例#1：
3
使用并查集，开一个一维数组存放每个人的敌人。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int fath[10007];
int n,m;
int vis[10007]; //存放敌人
void init()
{for(int i=1;i<=n;i++)fath[i]=i;for(int i=1;i<=n;i++)vis[i]=0;}
int find(int x)
{int r=x;while(r!=fath[r])r=find(fath[r]);int j;while(x!=r){j=fath[x];fath[x]=r;x=j;}return r;
}
int main()
{cin>>n;init();char c;int a,b;cin>>m;while(m--){cin>>c>>a>>b;if(c=='F') //如果是朋友{int fa=find(a);int fb=find(b);if(fa!=fb)fath[fa]=fb;}else //是敌人{if(vis[a]) //如果a有敌人，那么a的敌人和b就是朋友{int fa=find(vis[a]);int fb=find(b);if(fa!=fb)fath[fa]=fb;}if(vis[b])//如果b有敌人，那么a的敌人和a就是朋友{int fa=find(a);int fb=find(vis[b]);if(fa!=fb)fath[fa]=fb;}vis[a]=b;vis[b]=a;}}int cnt=0;for(int i=1;i<=n;i++){if(fath[i]==i)cnt++;}cout<<cnt<<endl;return 0;
}