openjudge T017 黑社会团伙（并查集）

1493: 黑社会团伙

Time Limit: 1 Sec Memory Limit: 128 MB

Description

众所周知，香港的黑社会组织猖獗，警方希望能摸清他们的内部构成情况，特派小生前往调查。经过长期的卧底，小生初步获得了一些资料：整个组织有n个人，任何两个认识的人不是朋友就是敌人，而且满足：

①我朋友的朋友是我的朋友；

②我敌人的敌人是我的朋友。

所有是朋友的人组成一个团伙。现在，警方委派你协助调查，拥有关于这n个人的m条信息（即某两个人是朋友，或某两个人是敌人），请你计算出这个城市最多可能有多少个团伙。

Input

第一行包含一个整数N，第二行包含一个整数M，接下来M行描述M条信息，内容为以下两者之一：“F x y”表示x与y是朋友；“E x y”表示x与y是敌人（1≤x≤y≤N）。

Output

包含一个整数，即可能的最大团伙数。

Sample Input

Sample Output

HINT

数据范围：2≤N≤2000，1≤M≤5000。

这道题思路很清晰，是一个团伙的人都插在一个集合里，

问题就在于我们如何判断两个人是不是一个团伙。

当两人是朋友，很容易判断他们是一个团伙。

当两个人是敌人，根据题意“敌人的敌人就是朋友”

我们就要弄清如何判断敌人的敌人

很多并查集里的题都用到一个思想，

用一个步骤点，来将集合连接

如果两个人是敌人那么连接，（x，y+n）和（y，x+n）

这样我们可以创造出一个不存在的人，来做他的朋友

当两个人的敌人相同时，他们的“不存在的朋友”就是相同的，就连接成了一个团伙了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int set1[10001];
int rank1[10001];
int data[10001];
int con[10001];
bool cmp(int a,int b)
{
    return a>b;
}
void Make_Set(int i)
{
    set1[i]=i;
    rank1[i]=0;
}
int find1(int i)
{ 
    if(set1[i]==i)
    return set1[i];
    return find1(set1[i]);        
}
void Union(int i,int j)
{
    i=find1(i);
    j=find1(j);
    if(i==j) 
    return;
    if(rank1[i]>rank1[j]) 
    set1[j]=i;
    else
    {
        if(rank1[i]==rank1[j]) 
        rank1[j]++;   
        set1[i]=j;
    }
}
int main()
{
    int n,m,x,y;
    char a;
    int i,j;
    scanf("%d%d",&n,&m);    
    for(i=1;i<=n*2;i++)
    {
        Make_Set(i);
    }
    for(i=1;i<=m;i++)
    {
        cin>>a;
        scanf("%d%d",&x,&y);
        if(a=='F')
        Union(x,y);
        if(a=='E')
        {
            Union(x,y+n);
            Union(y,x+n);
        }
    }
    int step,ans=0;
    for(i=1;i<=n*2;i++)
    con[i]=find1(i);
    sort(con,con+n+1,cmp);
    for(i=1;i<=n;i++)
    {
        if(con[i]!=con[i-1])
        ans++;
    }
    printf("%d",ans);
     
}

View Code