題目描述

      眾所周知，香港的黑社會組織猖獗，警方希望能摸清他們的內部構成情況，特派小生前往調查。經過長期的卧底，小生初步獲得了一些資料：整個組織有 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;
}