BZOJ1370：[Baltic2003]团伙

浅谈并查集：https://www.cnblogs.com/AKMer/p/10360090.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=1370

根据题目意思模拟，此题难点在于看懂题目。

时间复杂度：\(O(\alpha{n})\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;
#define A enemy[a]
#define B enemy[b]

const int maxn=1005;

char s[5];
int n,m,ans;
int fa[maxn],enemy[maxn];

int read() {
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}

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

void merge(int a,int b) {
    if(!a||!b)return;
    fa[find(a)]=find(b);
}

int main() {
    n=read(),m=read();
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1,a,b;i<=m;i++) {
        scanf("%s",s+1);
        a=read(),b=read();
        if(s[1]=='E') {
            if(b&&A)merge(b,A);
            else A=A+b;
            if(a&&B)merge(a,B);
            else B=B+a;
        }
        else merge(a,b);
    }
    for(int i=1;i<=n;i++)
        ans+=(fa[i]==i);
    printf("%d\n",ans);
    return 0;
}

BZOJ1370：[Baltic2003]团伙

原文：https://www.cnblogs.com/AKMer/p/10365880.html