【洛谷P1892】团伙

题目大意：维护 N 个人和 M 个关系，对每个人来说符合：我朋友的朋友也是我的朋友，我敌人的敌人也是我的朋友，求最多有多少个朋友构成的联通块。

题目大意：维护关系显然要用到并查集，这里是维护了两种关系，即：朋友和敌人，应该有两种做法，首先是维护带权并查集，可用 0 表示两人为朋友，1 表示两人为敌人，不过这样做似乎对于求有多少个朋友构成的联通块并不容易，因为只要两个人有关系（无论什么关系）都在一个联通块中；另一种做法就是扩展域并查集，将一个点拆成两个点，分别表示自己朋友的集合和自己敌人的集合，这样最后统计自己朋友的集合有多少联通块直接排序去重即可。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=1010;

int n,m,f[maxn<<1],a[maxn];
char opt[5];

int find(int x){
    return x==f[x]?x:f[x]=find(f[x]);
}

void read_and_parse(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n<<1;i++)f[i]=i;
}

void solve(){
    int x,y;
    while(m--){
        scanf("%s%d%d",&opt,&x,&y);
        if(opt[0]==‘F‘)f[find(x)]=find(y);
        else f[find(x)]=find(y+n),f[find(x+n)]=find(y);
    }
    for(int i=1;i<=n;i++)a[i]=find(i);
    sort(a+1,a+n+1);
    printf("%d\n",unique(a+1,a+n+1)-a-1);
}

int main(){
    read_and_parse();
    solve();
    return 0;
}

【洛谷P1892】团伙

原文：https://www.cnblogs.com/wzj-xhjbk/p/10019565.html