【题目大意】
在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足： 1、 我朋友的朋友是我的朋友； 2、 我敌人的敌人是我的朋友； 所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？
【思路】
水………NOIP的小孩都不屑于玩……
把i拆成i和i+n,其中i表示i的朋友，i+n表示i的敌人。对于(i,j):
(1)i，j是朋友，那么合并i和j。
(2)i，j不是朋友，那么合并i和j+n,j和i+n，代表敌人的敌人是我的朋友。
*注意，如果i和j是敌人，那么它们的敌人不一定是朋友。所有不要合并i+n和j+n。
好水啊……
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=;
int u[MAXN],h[MAXN],appear[MAXN];
int n,m,gang; int find(int x)
{
int r=x,temp;
while (u[r]!=r) r=u[r];
while (x!=r)
{
temp=u[x];
u[x]=r;
x=temp;
}
return r;
} void union_set(int fa,int fb)
{
if (h[fa]>=h[fb])
{
u[fb]=fa;
if (h[fa]==h[fb]) h[fa]++;
}
else u[fa]=fb;
} void init()
{
for (int i=;i<=*n;i++)
{
u[i]=i;
h[i]=;
}
} void solve()
{
scanf("%d%d",&n,&m);
init();
for (int i=;i<=m;i++)
{
char op[];
int u,v;
scanf("%s%d%d",op,&u,&v);
if (op[]=='F')
{
int fa=find(u),fb=find(v);
if (fa!=fb) union_set(fa,fb);
}
else
{
int fa=find(u),fb=find(v+n);
if (fa!=fb) union_set(fa,fb);
fa=find(v),fb=find(u+n);
if (fa!=fb) union_set(fa,fb);
}
}
} void getans()
{
for (int i=;i<=n;i++) u[i]=find(i);
memset(appear,-,sizeof(appear));
gang=;
for (int i=;i<=n;i++)
{
if (appear[u[i]]==-)
{
gang++;
appear[u[i]]=;
}
}
printf("%d",gang);
} int main()
{
solve();
getans();
return ;
}