并查集

· · 个人记录

我来总结一下自己对并查集的理解。

并查集其实是用来快速维护某种关系的一种数据结构，最近遇到了种类并查集和带权并查集。

P1892 [BOI2003]团伙

这道题考虑维护自己的朋友，fa[x]表示x的“祖先朋友”，其实，也可以直接理解为x的朋友。再考虑如何维护它们的关系。

可以把n*=2，分成两个集合，一个是A集合，一个是B集合。其中A集合和B集合互为敌人。比如，A集合的u与B集合的u互为的人，那么fa[u]与fa[u + n] 互为敌人

如果u和v是敌人，那么

u -> v（->表示敌对）

并且u -> u + n

u此时有两个敌人，将u的两个敌人合并；

还有一种情况：

v -> v + n , v - > u

那么，也将v的两个敌人合并。

至于代码，看题解的吧（跑）

种类并查集就是对自己的朋友进行合并，维护。

P2342 叠积木

将under[x]表示x下有多少积木，size[x]表示以x为“根”，这堆积木有多少个，fa[x]是x的“根”。

若要将x堆到y上，需要维护under值和size值，怎么维护看代码。在find中，因为只对根进行维护了，也要让其他值进行维护，所以在路径压缩中维护under值。

#include<bits/stdc++.h>

using namespace std;

const int N = 3e6 + 10;

int p;
char ins;
int x , y , z;
int fa[N] , under[N] , size[N];

inline int find(int x){
    if(fa[x] == x)
        return fa[x];
    int root = find(fa[x]);
    under[x] += under[fa[x]];
    return fa[x] = root;
}

int main(){
    ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);
    cin >> p;
    for(int i = 1 ; i <= N ; ++i)
        fa[i] = i , size[i] = 1 , under[i] = 0;
    for(int i = 1 ; i <= p ; ++i){
        cin >> ins;
        if(ins == 'M'){
            cin >> x >> y;
            int fx = find(x) , fy = find(y);
            under[fx] += size[fy];
            size[fy] += size[fx];
            fa[fx] = fy;
            size[fx] = 0;
        }
        else {
            cin >> z;
            find(z);//这里要再次find一下，因为如果上一次是合并操作的话，没有将其他值维护，以防万一。                 cout << under[z] << endl;
        } 
    }
    return 0;
}

带权并查集其实就是考虑将一些值进行维护。