[Baltic2003]gang團伙

[Baltic2003]gang團伙

Description
在某城市裡住著n個人,任何兩個認識的人不是朋友就是敵人,而且滿足:
1. 我朋友的朋友是我的朋友;
2. 我敵人的敵人是我的朋友;
所有是朋友的人組成一個團伙。告訴你關於這n個人的m條資訊,即某兩個人是朋友,或者某兩個人是敵人,請你編寫一個程式,計算出這個城市最多可能有多少個團伙?

Input
第1行為n和m,N小於1000,M小於5000; 以下m行,每行為p x y,p的值為0或1,p為0時,表示x和y是朋友,p為1時,表示x和y是敵人。

Output
一個整數,表示這n個人最多可能有幾個團伙。

Sample Input
6
4
E 1 4
F 3 5
F 4 6
E 1 2

Sample Output
3

HINT
{1},{2,4,6},{3,5}

Source

題解
並查集真水。
如果只有第一個條件,那麼這道題就非常水,可以說是裸題了。但是,第二個條件就比較麻煩了。為了解決這個問題,可以對每個人(記為x)構造一個“宿敵”x n。如果讀入的兩個人x和y是朋友,就將x和y放入一個集合。如果讀入的兩個人x和y是敵人,就將x和y n、x n和y連起來(因為敵人的敵人是朋友)。最後列舉1~n,尋找他們屬於多少個集合即可。
樣例圖:(這裡用橫線代表是朋友,用帶雙向箭頭的橫線代表是敵人)
這是樣例
處理後的樣例圖:(可以看出,畫圈的點分別屬於三個集合)
這是對於樣例的處理

標程

#include <cstdio>
#include <algorithm>
const int maxn=1000;
int fa[maxn*2 10],a[maxn 10];
int n,m,i,j,x,y,ans;
char c;
int find(int x)
{
return fa[x]==0?x:find(fa[x]);
}
int merge(int x,int y)
{
x=find(x);
y=find(y);
if (x!=y)
{
fa[x]=y;
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
for (i=1;i<=m;i  )
{
getchar();
scanf("%c%d%d",&c,&x,&y);
if (c=='F')
{
merge(x,y);//將x和y合併 
}
if (c=='E')
{
merge(x,y n);//將x和y n合併 
merge(x n,y);//將x n和y合併 
}
}
for (i=1;i<=n;i  )
{
a[i]=find(i);//尋找屬於哪一個並查集 
}
std::sort(a 1,a n 1);
ans=1;
for (i=2;i<=n;i  )
{
if (a[i]!=a[i-1])
{
ans  ;//計算屬於多少個並查集 
}
}
printf("%d\n",ans);
return 0;
}