$$并查集$$

• 1.初始化每个人的祖先就是自己
• 2.输入两个人,然后将两个人的祖先合并
• 3.输入,判断两个人的祖先是否相同(查找两个人的祖先是否相同)

并查集基本操作例题

//查询是否属于同一个集合
inline int find(int x){
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
//合并两个集合

inline void add(int x, int y){
    f[(find(x)] = f[find(y)]; 
}

并查集的其他用法(扩展域）:

• 当包含多重关系时,可以用个集合来表示各个关系
• 做法：一般会把集合 f的大小放大 t 倍(t个关系), f[N*t]

食物链

这题中包含 3 种关系 : 同类 天敌 猎物 ,故可以开 3 倍的集合

#include <cstdio>
using namespace std;
/*
x元素所在集合中所有∈[1，n]的元素都是x元素的同类
x+n元素所在集合中所有∈[1，n]的元素都是x元素的天敌
x+2n元素所在集合中所有∈[1，n]的元素都是x元素的猎物
*/

const int maxN = 100005;

int n, m, ans, fa[maxN * 3];

int find(int u) { return fa[u] == u ? u : fa[u] = find(fa[u]); }

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n * 3; i++) fa[i] = i;  //初始化
    while(m--) {
        cin >> opt >> u >> v;
        //判断是不是超过 n, 即判断是假话（如题目所言）
        if (u > n || v > n) { ans++; continue; }
        if (opt == 1) {
        //他们的关系是不是已经是天敌，(假话)
            if (find(u + n) == find(v) || find(u) == find(v + n)) { ans++; }
            else {
                fa[find(u)] = find(v);
                fa[find(u + n)] = find(v + n);
                fa[find(u + n + n)] = find(v + n + n);
            }
        }
        else {
        //他们的关系是不是同类，(假话)
            if (find(u) == find(v) || find(u) == find(v + n)) { ans++; }
            else {
                fa[find(u + n)] = find(v);
                fa[find(u + n + n)] = find(v + n);
                fa[find(u)] = find(v + n + n);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

反集的运用

团伙

类似的，这题的关系不止一种，所以集合大小要加倍，但是只有在是敌人的时候才互相连接，符合敌人的敌人是朋友的规则

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 2005;

int f[N];
int n, m,res;

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

void add(int x, int y){ f[find(x)] = f[find(y)];}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n * 2; i++) f[i] = i;
    for(int i = 1; i <= m; i++){
        char op[2];int x, y;
        scanf("%s",op); cin >> x >> y;

        if(op[0] == 'F')    add(x,y);
        else if(op[0] == 'E')   add(x + n, y),  add(y + n, x);
    }

    for(int i = 1; i <= n; i++) 
        if(f[i] == i) res ++;

    printf("%d\n",res);
    return 0;
}