C++如何实现带权重的并查集算法管理连通分量与元素权重

带权重的并查集在传统并查集的基础上，为每个节点增加了与父节点的权重偏移量，既能够高效判断两个元素是否属于同一个连通分量，也能快速计算出两个元素之间的权重差值，在很多需要关联关系和数值计算的场景中有广泛应用。

带权并查集的核心设计

带权并查集需要维护两个核心数组，分别是父节点数组和权重数组。父节点数组用来记录每个元素的直接父节点，权重数组用来记录当前元素相对于其父节点的权重值。当执行查找操作时，会同时进行路径压缩，更新节点的父节点为根节点，并同步修正权重值，保证权重信息的正确性。

核心属性定义

我们可以用一个类来封装带权并查集的所有逻辑，核心属性如下：

• parent数组：存储每个节点的父节点，初始时每个节点的父节点为自己
• weight数组：存储每个节点相对于其父节点的权重，初始时所有节点的权重为0
• size属性：记录当前并查集的元素总数量

核心方法实现

初始化方法

初始化时需要为每个元素设置独立的父节点，权重初始为0，每个元素默认属于独立的连通分量。

#include <vector>
#include <iostream>
using namespace std;

class WeightedUnionFind {
private:
    vector<int> parent;  // 父节点数组
    vector<int> weight;  // 节点相对于父节点的权重
    int n;               // 元素总数量

public:
    // 初始化带权并查集，元素数量从0到n-1
    WeightedUnionFind(int size) {
        n = size;
        parent.resize(n);
        weight.resize(n, 0);
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // 初始父节点为自己
        }
    }
};

查找根节点方法

查找操作需要递归找到元素的根节点，同时完成路径压缩。在回溯过程中，需要将当前节点的权重更新为相对于根节点的权重，保证后续计算的正确性。

// 查找元素x的根节点，同时更新x的权重为相对于根节点的权重
int find(int x) {
    if (parent[x] != x) {
        int root = find(parent[x]);  // 先找到根节点
        // 当前节点的权重 = 当前节点相对于父节点的权重 + 父节点相对于根节点的权重
        weight[x] += weight[parent[x]];
        parent[x] = root;  // 路径压缩，父节点直接指向根节点
    }
    return parent[x];
}

合并两个元素方法

合并操作需要先将两个元素的根节点找到，如果根节点不同，就需要将一个根节点挂载到另一个根节点下，同时计算新的权重值，保证两个元素之间的权重关系符合要求。

假设我们已知元素x和元素y之间的权重差为w，即x的权重减去y的权重等于w，合并时的权重计算逻辑如下：

设x的根节点为rx，y的根节点为ry，x相对于rx的权重为wx，y相对于ry的权重为wy。合并后ry的父节点设为rx，那么ry相对于rx的权重需要满足：wx - (wy + weight[ry]) = w，推导得到weight[ry] = wx - wy - w。

// 合并元素x和元素y，已知x的权重 - y的权重 = w
bool unite(int x, int y, int w) {
    int rx = find(x);
    int ry = find(y);
    if (rx == ry) {
        // 已经属于同一个连通分量，不需要合并
        return false;
    }
    // 计算ry相对于rx的权重
    weight[ry] = weight[x] - weight[y] - w;
    parent[ry] = rx;  // 将ry的父节点设为rx
    return true;
}

判断连通性与计算权重差

判断两个元素是否连通只需要看它们的根节点是否相同，计算两个元素的权重差则需要先确认它们属于同一个连通分量，再用各自的相对根节点权重做差即可。

// 判断x和y是否属于同一个连通分量
bool isConnected(int x, int y) {
    return find(x) == find(y);
}

// 计算x的权重 - y的权重，如果不属于同一个连通分量返回特殊值-1
int getWeightDiff(int x, int y) {
    if (!isConnected(x, y)) {
        return -1;
    }
    // x的相对根权重 - y的相对根权重就是两者的权重差
    return weight[x] - weight[y];
}

完整源码与使用示例

下面是带权并查集的完整实现代码，包含上述所有方法，同时附带一个简单的使用示例。

#include <vector>
#include <iostream>
using namespace std;

class WeightedUnionFind {
private:
    vector<int> parent;
    vector<int> weight;
    int n;

public:
    WeightedUnionFind(int size) {
        n = size;
        parent.resize(n);
        weight.resize(n, 0);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

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

    bool unite(int x, int y, int w) {
        int rx = find(x);
        int ry = find(y);
        if (rx == ry) {
            return false;
        }
        weight[ry] = weight[x] - weight[y] - w;
        parent[ry] = rx;
        return true;
    }

    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }

    int getWeightDiff(int x, int y) {
        if (!isConnected(x, y)) {
            return -1;
        }
        return weight[x] - weight[y];
    }
};

int main() {
    // 初始化5个元素的带权并查集
    WeightedUnionFind wuf(5);
    // 合并0和1，0的权重 - 1的权重 = 2
    wuf.unite(0, 1, 2);
    // 合并1和2，1的权重 - 2的权重 = 3
    wuf.unite(1, 2, 3);

    cout << "0和2是否连通：" << (wuf.isConnected(0, 2) ? "是" : "否") << endl;
    cout << "0的权重 - 2的权重：" << wuf.getWeightDiff(0, 2) << endl;

    // 尝试合并3和4，3的权重 - 4的权重 = 1
    wuf.unite(3, 4, 1);
    cout << "0和3是否连通：" << (wuf.isConnected(0, 3) ? "是" : "否") << endl;
    return 0;
}

算法复杂度分析

带权并查集的查找和合并操作在路径压缩的优化下，时间复杂度接近O(1)，和普通的并查集性能基本一致。空间复杂度为O(n)，需要存储n个元素的父节点和权重信息。这种算法非常适合处理大量元素的连通关系与权重关联查询场景，比如食物链问题、差分约束问题的简化版本等。

C++带权并查集连通分量元素权重管理union_find修改时间：2026-06-25 11:36:41