题解 P1892 【团伙】

zzzyc · 2017-09-03 15:15:46 · 题解

并查集。。。。。。。。。。。。。。。

#include <iostream>
#include <cstdio>
using namespace std;
int fa[1010]; //记录团伙头目。。。（感觉这个强盗是家族产业，毕竟是father） 
bool fight[1010][1010]; //仇敌关系的说,打架。。。 
int find(int x) //寻找根节点。 
{
    if (fa[x]!=x) fa[x]=find(fa[x]); //路径压缩
    return fa[x];
}
void unionn(int x,int y) //合并x和y所在集合
{
    int f1=find(x);
    int f2=find(y);
    if (f1!=f2) fa[f2]=f1;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        fa[i]=i; //预处理并查集。 
    for(int asdf=1;asdf<=m;asdf++) //asdf纯属丧心病狂。。。 
    {
        char h;
        int a,b;
        cin>>h>>a>>b;
        if (h=='F') unionn(a,b); //如果是朋友直接合并
        else //否则是敌人  
        {
            fight[a][b]=fight[b][a]=true; //仇敌关系
            for (int i=1;i<=n;i++) //检查所有强盗，因为很菜不会套路，本以为要GG的。 
            {
                if (fight[a][i]) unionn(b,i); //a和k是敌人，又因为a和b是敌人，所以b和k是朋友 
                if (fight[b][i]) unionn(a,i); //同上
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        if(fa[i]==i)
            ans++; //统计团伙个数（也就是树根）
    printf("%d\n",ans);
    return 0;
}