BZOJ 1370 [Baltic2003]Gang团伙

题目大意

给你一些人，他们之间保证一些关系：敌人的敌人是我的朋友，朋友的朋友是我的朋友。问最终有多少朋友关系构成的团伙。

首先我们建立一个普通的并查集，之后考虑如何实现“敌人的敌人是我的朋友”。

因为“敌人的朋友不一定是我的敌人”，所以类似这种情况必须不同对待，考虑对于敌人和朋友建立不同的并查集网络。把每个人拆成2个点，如果它们是敌人那么就互相向对面的“敌人点”连边，如果是朋友那么就向对面的主要点直接连边。

最终求答案的时候直接对于每个主点进行一次并查集查询操作，求出共有多少个不同的father就可以了。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,x,y,ans,a[10010],fa[10010];
char mode[10];
int unifind(int tx)
{
	if(!fa[tx]||fa[tx]==tx) return tx;
	return fa[tx]=unifind(fa[tx]);
}
void unimerge(int tx,int ty)
{
	tx=unifind(tx),ty=unifind(ty);
	if(tx!=ty) fa[tx]=ty;
}
int main()
{
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%s%d%d",mode,&x,&y);
		switch(mode[0])
		{
			case 'F': unimerge(x,y);break;
			case 'E': unimerge(x,y+n),unimerge(x+n,y);break;
		}
	}
	for(int i=1;i<=n;++i) a[i]=unifind(i);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;++i) if(i==1||a[i]!=a[i-1]) ++ans;
	printf("%d\n",ans);
	return 0;
}