Void-7's

洛谷P1892 [BIO2003] 团伙

算法 [**洛谷P1892 BIO2003] 团伙**

并查集的模板题。注释两行最重要。

#include<iostream>

using namespace std;

int fa[1010];
int ea[1010];

void makeSet(int n){
    for(int i=0;i<n;i++) fa[i]=i;
    for(int i=0;i<n;i++) ea[i]=0;
}

int find(int x){
    if(fa[x]!=x){
        fa[x]=find(fa[x]);
    }
    return fa[x];
}

void uni(int x,int y){
    int fx=find(x);int fy=find(y);
    if(fx!=fy) fa[fx]=fy;
}

int main(){
    int n,m;
    cin>>n>>m;
    makeSet(n);
    for(int i=0;i<m;i++){
        string x;int a,b;
        cin>>x>>a>>b;
        if(x=="F"){
            uni(a,b);
        }else{
            if(!ea[b]) ea[b]=a;//如果b之前没有敌人,将a设为b的敌人
            else uni(a,ea[b]);//否则,合并a与“b的敌人”
            if(!ea[a]) ea[a]=b;
            else uni(b,ea[a]);
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        if(fa[i]==i) ans++;
    }
    cout<<ans;
    return 0;
}