带权并查集详解

一、什么是并查集

并查集（DisjointSet）是一种树型的数据结构，用于处理一些不相交的集合（Disjoint Sets）。通常支持如下几种操作：

• 初始化
• 查找元素所在集合
• 合并两个集合

class DisjointSet {
public:
    DisjointSet(int n) {
        for(int i=0; i<n; i++) {
            parent[i] = i;
        }
    }
    int Find(int x) {
        if(parent[x]==x) return x;
        return parent[x] = Find(parent[x]);
    }
    void Union(int x, int y) {
        int root_x = Find(x), root_y = Find(y);
        if(root_x!=root_y) parent[root_x] = root_y;
    }
private:
    int parent[MAX];
} ds(MAX);

二、带权并查集的概念

带权并查集（Weighted Disjoint Set）是在普通并查集的基础上，每个集合还有一个权值的概念，用来表示这个集合中的元素之间的某种关系，例如长度等。

三、带权并查集的变化

1. 表示元素之间的关系

在普通并查集中，集合中的元素之间没有特定的关系，每个元素只有属于哪个集合的信息。而在带权并查集中，每个集合增加了一个权值，用于表示集合中元素之间的某种关系。

2. 查找最值

在带权并查集中，由于集合中的元素之间存在关系，那么可以在查找集合的同时，求出集合中权值的最大值或最小值。

3. 路径压缩时同时维护权值的信息

在路径压缩时，如果要将元素的父节点设为根节点，那么根据路径压缩的方式，该节点的祖先节点权值可能会丢失。因此需要维护每个节点祖先节点的权值信息，以便查找时能够找到根节点并计算正确的权值.

class WeightedDisjointSet {
public:
    WeightedDisjointSet(int n) {
        for(int i=0; i<n; i++) {
            parent[i] = i;
            rank[i] = 0;
            weight[i] = 0;
        }
    }
    int Find(int x) {
        if(parent[x]==x) return x;
        int root = Find(parent[x]);
        weight[x] += weight[parent[x]]; // 维护权值信息
        return parent[x] = root;
    }
    void Union(int x, int y, int w) {
        int root_x = Find(x), root_y = Find(y);
        if(root_x!=root_y) {
            if(rank[root_x]>rank[root_y]) {
                parent[root_y] = root_x;
                weight[root_y] = w - weight[y] + weight[x]; // 更新权值
            } else {
                parent[root_x] = root_y;
                weight[root_x] = -w + weight[y] - weight[x]; // 更新权值
                if(rank[root_x]==rank[root_y]) rank[root_y]++;
            }
        }
    }
private:
    int parent[MAX], rank[MAX], weight[MAX];
} wds(MAX);

四、带权并查集的应用

1. Kruskal算法

Kruskal算法是一种用于求带权图的最小生成树（Minimum Spanning Tree）的算法。具体思路是将边按照权值从小到大排序，然后依次考虑每条边，如果这条边的两个端点不在同一个集合中，则将它们所在的集合合并，并将这条边加入到最小生成树的边集中。

struct Edge {
    int u, v, w;
    bool operator<(const Edge& e) const {
        return w < e.w;
    }
};
vector<Edge> edges; // 存储边的集合
int kruskal(int n) {
    sort(edges.begin(), edges.end());
    WeightedDisjointSet wds(n);
    int ans = 0;
    for(int i=0; i<edges.size(); i++) {
        Edge& e = edges[i];
        if(wds.Find(e.u)!=wds.Find(e.v)) {
            wds.Union(e.u, e.v, e.w);
            ans += e.w;
        }
    }
    return ans;
}

2. 求连通块大小

可以利用带权并查集的合并操作求出连通块的大小。

int cnt = 0;
for(int i=0; i<n; i++) {
    if(wds.Find(i)==i) {
        cnt++;
    }
}

3. 求连通块中的最大最小值

可以在查找集合的同时，维护最大最小值。

int Find(int x) {
    if(parent[x]==x) return x;
    int root = Find(parent[x]);
    max_val[x] = max(max_val[x], max_val[parent[x]]);
    min_val[x] = min(min_val[x], min_val[parent[x]]);
    return parent[x] = root;
}