【数据结构】带权并查集

目录

• 简介
• 详细介绍
• 例题

简介

顾名思义，就是在维护集合关系的树中添加边权的并查集，这样做可以维护更多的信息。

引入题目：https://www.luogu.com.cn/problem/P2024
比如这道题，如果使用普通的并查集则无法处理，因为普通的并查集只能够刻画两个物品是否属于同一个集合。因此这时候就要使用能够记录更多信息的）

#include<bits/stdc++.h>
using namespace std;

const int N=5e4+5;

int f[N],d[N];

int find(int x){
    if(x!=f[x]){
        int root=find(f[x]);
        d[x]+=d[f[x]];
        f[x]=root;
    }
    return f[x];
}

int main(){
    int n,m;
    cin>>n>>m;

    for(int i=1;i<N;i++) f[i]=i;

    int cnt=0;
    while(m--){
        int op,a,b;
        cin>>op>>a>>b;

        //2,3 judge
        if(a>n || b>n){
            cnt++;
            continue;
        }
        if(a==b && op==2){
            cnt++;
            continue;
        }

        int pa=find(a),pb=find(b);

        int t= op==2;
        if(pa==pb){
            if(((d[a]-d[b])%3+3)%3!=t) cnt++;
        }else{
            f[pa]=pb;
            d[pa]=t+d[b]-d[a];
        }
    }

    cout<<cnt<<endl;

    return 0;
}

例题

https://www.acwing.com/problem/content/241/
分析：思路完全类似于食物链那题。