带权并查集的实现与应用

并查集（Union-Find）是一种高效的数据结构，广泛应用于并查、查找、路径压缩等操作。其中，带权并查集通过记录节点与其父亲节点的关系，能够更高效地处理复杂的合并操作。

在本文中，我们将介绍带权并查集的实现方法及其应用场景。

基本思路

在带权并查集中，我们用 rank[x] 记录节点 x 与其父亲节点之间的关系。具体来说：

rank[x] = 0 表示 x 与其父亲属于同一个类。

rank[x] = 1 表示 x 的父亲节点吃掉 x。

rank[x] = 2 表示 x 吃掉其父亲节点。

通过递归路径压缩和按秩合并，我们可以实现高效的并查操作。

代码实现

#include 
   
    
#include 
    
     
#define MAXN 50010
using namespace std;
int rank[MAXN], pre[MAXN];
int find(int x) {
    if (pre[x] != x) {
        int px = find(pre[x]);
        rank[x] = (rank[x] + rank[pre[x])) % 3;
        pre[x] = px;
    }
    return pre[x];
}
int jion(int x, int y, int d) {
    int px = find(x);
    int py = find(y);
    if (px == py) {
        if ((rank[y] - rank[x] + 3) % 3 != d) {
            return 1;
        }
    } else {
        pre[py] = px;
        rank[py] = (rank[x] - rank[y] + d + 3) % 3;
    }
    return 0;
}
int main() {
    int n, k, ans = 0;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < MAXN; i++) {
        rank[i] = 0;
        pre[i] = i;
    }
    while (k--) {
        int d, x, y;
        scanf("%d%d%d", &d, &x, &y);
        if (x > n || y > n) {
            ans++;
        } else if (d == 2 && x == y) {
            ans++;
        } else {
            ans += jion(x, y, d - 1);
        }
    }
    printf("%d\n", ans);
    return 0;
}

代码解释

初始化：我们初始化 rank 和 pre 数组。rank[x] 记录节点 x 与其父亲节点的关系，pre[x] 记录节点 x 的父亲节点。

查找函数 find：

递归查找节点 x 的根节点。

路径压缩：将 x 的父亲节点直接指向根节点。

更新 rank[x]：根据路径压缩的结果，更新 rank[x]。

合并函数 jion：

查找 x 和 y 的根节点。

如果根节点相同，验证 rank 的关系是否符合 d。

如果关系不符，按秩合并，更新 pre 和 rank 数组。

主函数 main：

读取输入 n 和 k。

初始化 rank 和 pre 数组。

处理每个查询，调用 jion 函数计算答案。

应用场景

带权并查集广泛应用于以下场景：

图的连通性问题：用于判断图中是否存在环。

矩阵的秩问题：用于判断矩阵是否是秩为 1 的矩阵。

路径问题：用于解决路径压缩和路径长度查询。

通过带权并查集，我们可以高效地处理复杂的并查和查找操作，适用于大规模数据的处理。

转载地址：http://abxfk.baihongyu.com/

你可能感兴趣的文章