并查集

· · 个人记录

并查集 update on 2023/1/14 (\%100/\%100)

Tips：并查集真的真的不难

零、并查集的用法

众所周知并查集是一个很简单的东西
只需要用你的亿点点观察能力and注意力就so easy
并查集=并+查（合并+查询）
并查集往往用树来存，使用fa数组表示每个节点的父节点,初始fa[i]=i,合并x,y时只需将x树的根节点与y树的根节点连线即可合并，查询x的根节点可以使用find(x)函数求得。
查:

int fa[];//存储每个节点的父节点
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
    //fa[x] = find(fa[x])路径压缩
    //将所有节点的父节点变成这棵树的根节点
}

等等，让我们来感性理解一下
路径压缩:

每个节点find后都会指向这棵树的根节点，使每次find时，节点只需一次即可到达根节点

并:

int fa[];
int find(int x){}
//同上“查”
void merge(int x , int y){
    int rx = find(x) , ry = find(y);
    if(rx == ry) return;
    //若根节点相同为同一集合不用合并
    fa[ry] = rx;//fa[rx] = ry; 两者选一
    //将两棵树的根节点连线
    return;
}

让我们继续来感性理解一下
合并操作:

在主函数记得初始化:

int main(){
    for(int i = 1; i <= n; i++) fa[i] = i;
    //初始化
    ......
    return 0;
}

一、朴素并查集（又称普通并查集或并查集）

照抄上述代码即可
P1551 亲戚
太简单了不想讲解了
代码如下:

int n , m , p , fa[];
int find(int x){}
void merge(int x , int y){}
//并查集
int main(){
    cin >> n >> m >> p;
    for(int i = 1; i <= n; i++) fa[i] = i;//初始化
    while(m--){
        int u , v;
        cin >> u >> v;
        //合并u,v
    }
    while(p--){
        int u , v;
        cin >> u >> v;
        if(/*是亲戚*/) puts("Yes");
        else puts("No");
    }
    return 0;
}

二、种类并查集

前面说的是朴素并查集（也可以是普通并查集or并查集），而有时候数据给的很过分，多种物品有多种关系，有可能是互为敌人or互为队友，那就需要使用到我们的种类并查集了，其实它就是多个并查集组成，若a,b互为敌人，就将a本身和b的敌人形态合并即可。
如:P1525 [NOIP2010 提高组] 关押罪犯有敌人和朋友两种关系，先按照c从大到小排序，后面就是种类并查集。代码如下:

int n , m , f[];
int find(int x){}
void merge(int x , int y){}
//前面都一样
struct node{
    int a , b , c;
}x[];
bool cmp(node x , node y){}//cmp函数我就不给了
int main(){
    __________;
    //输入+初始化
    sort(x + 1 , x + 1 + m , cmp);//排序
    for(int i = 1; i <= m; i++){
        int a = x[i].a , b = x[i].b , c = x[i].c;
        if(find(a) == find(b) || find(a + n) == find(b + n)){
            cout << c;
            return 0;
        }//若为同一监狱直接输出c
        merge(a , b + n);
        merge(b , a + n);
        //合并
    }
    cout << 0;//不会发生冲突
    return 0;
}

三、带权并查集

带权并查集就是每个节点或都有一个或多个权值需要在合并or查询时维护这些权值即可
如P1196 [NOI2002] 银河英雄传说可以维护一个pre数组，pre[x]表示x离根结点的距离，那么ans=abs(pre[x] - pre[y]) - 1，但若需要维护pre数组就必须有一个num数组每次merge时pre[ry] += num[ry]，num[x]表示以x作为根节点的树的节点数量，在find和merge时就可以加上一个值，从而维护pre数组求得ans。
具体代码如下:

int fa[] , pre[] , num[];
int find(int x){
    if(fa[x] == x) return x;      
    int rx = find(fa[x]); 
    pre[x] += pre[fa[x]]; 
    return fa[x] = rx;    
}
void marge(int x , int y){
    int rx = find(x) , ry = find(y);
    pre[rx] += num[ry];
    num[ry] += num[rx];
    fa[rx] = ry;
    num[rx] = 0;
    return;
}

好了，并查集就是以上内容了

下期内容——搜索

本文图片均来自百度搜索