黑社會團伙（gangs），黑社會團伙gangs
題目描述
眾所周知，香港的黑社會組織猖獗，警方希望能摸清他們的內部構成情況，特派小生前往調查。經過長期的臥底，小生初步獲得了一些資料：整個組織有 n 個人，任何兩個認識的人不是朋友就是敵人。
而且滿足：①我朋友的朋友是我的朋友；②我敵人的敵人是我的朋友。所有是朋友的人組成一個團伙。
現在，警方委派你協助調查，擁有關於這 n 個人的 m 條信息（即某兩個人是朋友，或某兩個人是敵人） ，請你計算出這個城市最多可能有多少個團伙。
數據范圍
2≤N≤2000，1≤M≤5000。
輸入輸出格式
輸入描述：
第一行包含一個整數 N，第二行包含一個整數 M，接下來 M 行描述 M 條信息。
內容為以下兩者之一：“F x y”表示 x 與 y 是朋友；“E x y”表示 x 與 y 是敵人（1≤x≤y≤N） 。
輸出描述：
包含一個整數，即可能的最大團伙數。
輸入輸出樣例
輸入樣例：
6
4
E 1 4
F 3 5
F 4 6
E 1 2
輸出樣例：
3
思路
並查集。用1—n表示朋友，若p[0]==F，則unionn(x,y);用n+1—2*n表示敵人，若p[0]==E，則unionn(x,y+n),unionn(y,x+n)。
代碼
![]()
#include<stdio.h>
#include<string.h>
int a[5000];
char p[10];
int find(int x)
{
if(a[x]!=x)
x=find(a[x]);
return a[x];
}
void unionn(int x,int y)
{
x=find(x);
y=find(y);
a[y]=x;
}
int main()
{
int n,m,x,y,i,j,z,k=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n*2;i++)
a[i]=i;
for(i=1;i<=m;i++)
{
scanf("%s%d%d",p,&x,&y);
if(p[0]=='F')
unionn(x,y);
if(p[0]=='E')
{
unionn(x,y+n);
unionn(y,x+n);
}
}
for(i=1;i<=n;i++)
a[i]=find(i);
for(i=1;i<n;i++)
for(j=1;j<=n-i;j++)
if(a[j]>a[j+1])
{
z=a[j];
a[j]=a[j+1];
a[j+1]=z;
}
for(i=1;i<=n;i++)
if(a[i]!=a[i-1])
k++;
printf("%d",k);
return 0;
}
View Code
