至今头条

【模板】并查集

2024-01-25 13:05 由 意外路过的番茄酱骑士 发表于 #其他

　　并查集是解决两元素是否属于同一集合，将一个集合合并另一集合的数据结构。具体来说，我们使用数字代替集合，比如集合1，集合2.使用数组f[i]维护元素i属于的集合，比如f[2] = 4表示元素2属于集合4。具体我们有以下实现功能的代码

1 初始化表示集合的数组。

    cin>>n>>m;
    for(int i=1; i<=n; i++)
        f[i]=i;

 

 　　表示元素i属于集合i，也就是说开始每个元素都是散开的。

2 实现查找功能的find()函数

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

具体说明以下怎么实现的查找到的根结点（图有点丑）

 

 以结点d为例，假设我们查找结点d属于那个集合也就是查找到这颗树的根结点。

从系统栈层面解释。

 

 可以看到到达结点a之后，返回栈开始返回。

 结点a从上到下赋值给路径上的所有结点。那么这棵树就变成这样。

 这就是路径压缩。

3 合并函数join()

void join (int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx!=fy)     f[fx]=fy;
};

 

　　假设合并元素x，y所在集合首先find(x),find(y)找到元素x，元素y属于那个集合。

　然后将f[fx] 赋值为 fy，也就是x所在集合加入y所在集合。

 实现了合并。

 4 维护特征的并查集（带权并查集）

　　例题：837. 连通块中点的数量 https://www.acwing.com/problem/content/839/

　　只需要多增加一个数组siz[]来储存集合i的大小即可。初始化siz[i] = 1;

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
int n,m;

int f[maxn],size_f[maxn];

int find(int x){
    if(f[x] != x) return f[x] = find(f[x]);
    else return f[x];
}

void join(int x,int y){
    int x1 = find(x),y1 = find(y);
    if(x1 != y1) {
        size_f[y1] += size_f[x1]; // 主要维护集合fy的大小。
        f[x1] = y1;
    }
}
signed main ()
{
    cin>>n>>m;
    
    for(int i = 1; i<= n; i++){
        f[i] = i;
        size_f[i] = 1;
    }
    while(m--){
        string op;
        cin>>op;
        if(op == "C"){
            int a,b;
            cin>>a>>b;
            join(a,b);
        }else if(op == "Q1"){
            int a,b;
            cin>>a>>b;
            printf(find(a) == find(b) ? "Yes\n":"No\n");
        }else if(op == "Q2"){
            int a;
            cin>>a;
            printf("%d\n",size_f[find(a)]);
        }
    }
    return 0;
}

 

 

热门相关：锦绣医妃之庶女凰途   霸宠天下：腹黑帝君妖娆后   锦衣当国   暖君   暖君