bzoj1370 團伙 【並查集】

NO IMAGE

題目描述

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

輸入格式

第 1 行為 n 和 m ,其中 1

輸出格式

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

樣例資料 1

輸入
6 4
1 1 4
0 3 5
0 4 6
1 1 2

輸出
3

備註

【樣例說明】
{1},{2,4, 6},{3,5} 共 3 個團伙。

解題報告:

並查集實現,演算法如下:
1、如果 x 和 y 是朋友,則把 x 和 y 合併為一個團伙。
2、如果 x 和 y 是敵人,則繼續判斷:
(1)如果 x 的敵人 z 存在,在把 z 和 y 合併為一個團伙。因為敵人的敵人是朋友。
(2)如果 y 的敵人 z 存在,在把 z 和 x 合併為一個團伙。因為敵人的敵人是朋友。
3、統計團伙數量即可(即fa[x]=x的個數)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int getint()
{
int i=0,f=1;char c;
for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=getchar())i=(i<<3) (i<<1) c-'0';
return i*f;
}
const int N=1005;
int n,m,ans,fa[N],en[N][N];
int getfa(int x)
{
return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
void merge(int x,int y)
{
int fx=getfa(x),fy=getfa(y);
if(fx!=fy)fa[fy]=fx;
}
int main()
{
//freopen("lx.in","r",stdin);
int op,x,y;
n=getint(),m=getint();
for(int i=1;i<=n;i  )fa[i]=i;
while(m--)
{
op=getint(),x=getint(),y=getint();
if(op==0)merge(x,y);
else
{
for(int z=1;z<=n;z  )
if(en[x][z])merge(y,z);
for(int z=1;z<=n;z  )
if(en[y][z])merge(x,z);
en[x][y]=en[y][x]=1;
}
}
for(int i=1;i<=n;i  )
if(fa[i]==i)ans  ;
cout<<ans;
return 0;
}