并查集例题

LX01

• 题目传送门

长按鼠标左键并向右拖动有惊喜

# include<bits/stdc++.h>
using namespace std;

int n,m,fa[2001]; 

int find(int x){  //合并操作
    if(fa[x]!=x) fa[x]=find(fa[x]); 
    return fa[x];
}

void hebin(int x,int y) { //查找操作
    x=find(x);y=find(y); 
    fa[y]=x;
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=2*n;i++) fa[i]=i; //初始赋值
    for(int i=1;i<=m;i++){
        int p,q;
        char c;
        cin>>c>>p>>q;
        if(c=='F') hebin(p,q); //合并朋友的圈子 
        else hebin(q,p+n),hebin(p,q+n); //合并敌人的敌人的圈子
    }
    int ans=0;
    for(int i=1;i<=n;i++) if(fa[i]==i) ans++;
    printf("%d",ans);
    return 0;
 }