帶權並查集詳解

一、什麼是並查集

並查集（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;
}