您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

不相交集 (Union-Find) C++ 完整實現：從基礎到按秩/路徑壓縮優化

編輯：關於C++

不相交集（Disjoint Set Union, DSU / Union-Find）是解決動態連通性、Kruskal 最小生成樹、網絡連通分量等問題的核心數據結構。本文從等價關係理論出發，逐步推導數組表示、樹結構、按秩合並、路徑壓縮優化，並給出生產級 C++ 模板實現與測試用例。

一、理論基礎：等價關係與動態連通性

等價關係：滿足自反性 (a~a)、對稱性 (a~b ⇒ b~a)、傳遞性 (a~b ∧ b~c ⇒ a~c)。
等價類：某元素所在等價關係下的全體元素集合。
動態等價性問題：支持兩種操作 —— Find(x) 返回 x 所在集合代表元；Union(x, y) 合併 x、y 所在集合。在線處理序列操作。

二、數據結構演進

1. 數組直連法 (Quick-Find)

id[i] 直接存儲集合 ID。Find O(1)，Union 需掃描整個數組修改 ID，O(N)。

2. 鏈表法

每集合維護一個鏈表，Union 將短鏈表接到長鏈表尾，O(1) 合併（維護長度），但 Find 需遍歷到表頭，O(N)。

3. 樹結構 (Parent Pointer) —— 標準表示

每個元素指向父節點，根節點 parent[root] = -1 (或負值存儲尺寸/高度)。集合標識 = 根節點索引。
Find(x) 遞歸/迭代上溯到根；Union(r1, r2) 將一棵樹根掛到另一棵樹根下。

// 初始化：每個元素自成一棵樹
vector parent(n, -1); // 負值表示根且 |值| = 樹大小/高度

int Find(int x) {
    return parent[x] < 0 ? x : Find(parent[x]); // 簡單遞歸
}
void Union(int r1, int r2) {
    parent[r2] = r1; // 任意合併，樹高可能退化為 O(N)
}

三、兩大優化策略：按秩合並 + 路徑壓縮

1. 按秩合並 (Union by Rank / Size)

總是將較淺/較小的樹合併到較深/較大的樹下，保證樹高 ≤ log₂N。
實現：根節點存儲負的尺寸 (Size) 或高度 (Rank/Height)。

// 按尺寸合並 (推薦，實現更簡單)
void UnionBySize(int r1, int r2) {
    if (parent[r2] < parent[r1]) swap(r1, r2); // r1 尺寸更大 (更負)
    parent[r1] += parent[r2]; // 更新尺寸
    parent[r2] = r1;          // r2 掛到 r1 下
}

// 按高度合並
void UnionByRank(int r1, int r2) {
    if (parent[r2] < parent[r1]) swap(r1, r2); // r1 更高 (更負)
    if (parent[r1] == parent[r2]) parent[r1]--; // 高度相同，合併後高度+1
    parent[r2] = r1;
}

2. 路徑壓縮 (Path Compression)

Find 過程中，將路徑上所有節點直接掛到根下，攤還後 Find 接近 O(1) (反阿克曼函數 α(N))。

// 遞歸版 (簡潔)
int Find(int x) {
    return parent[x] < 0 ? x : parent[x] = Find(parent[x]);
}

// 迭代版 (無棧溢出風險)
int Find(int x) {
    int root = x;
    while (parent[root] >= 0) root = parent[root];
    while (x != root) {
        int next = parent[x];
        parent[x] = root;
        x = next;
    }
    return root;
}

四、完整生產級模板實現

#include 
#include 
#include 

class DisjointSet {
    std::vector parent_; // 負值：根節點，絕對值 = 尺寸
public:
    explicit DisjointSet(size_t n = 0) : parent_(n, -1) {}

    // 核心操作
    int Find(int x) {
        if (x < 0 || x >= (int)parent_.size()) throw std::out_of_range("Index out of range");
        return parent_[x] < 0 ? x : parent_[x] = Find(parent_[x]); // 路徑壓縮
    }

    bool Union(int x, int y) { // 按尺寸合並 + 路徑壓縮
        int rx = Find(x), ry = Find(y);
        if (rx == ry) return false; // 已在同一集合
        if (parent_[ry] < parent_[rx]) std::swap(rx, ry); // rx 尺寸更大
        parent_[rx] += parent_[ry];
        parent_[ry] = rx;
        return true;
    }

    // 輔助查詢
    bool Connected(int x, int y) { return Find(x) == Find(y); }
    size_t Size(int x) { return static_cast(-parent_[Find(x)]); }
    size_t Count() const { // 集合總數
        size_t cnt = 0;
        for (int v : parent_) if (v < 0) ++cnt;
        return cnt;
    }

    // 調試輸出
    void PrintSets() const {
        std::cout << "Parent array: ";
        for (int v : parent_) std::cout << v << ' ';
        std::cout << "\nSets:\n";
        std::vector printed(parent_.size(), false);
        for (size_t i = 0; i < parent_.size(); ++i) {
            if (parent_[i] < 0) {
                std::cout << "Root " << i << " (size " << -parent_[i] << "): ";
                for (size_t j = 0; j < parent_.size(); ++j)
                    if (Find(j) == (int)i) std::cout << j << ' ';
                std::cout << '\n';
            }
        }
    }
};

// 測試主程序
int main() {
    DisjointSet ds(10); // 0~9

    ds.Union(0, 1); ds.Union(2, 3); ds.Union(1, 2); // 0-1-2-3 連通
    ds.Union(4, 5); ds.Union(6, 7); ds.Union(4, 6); // 4-5-6-7 連通
    ds.Union(8, 9);                                 // 8-9 連通

    std::cout << "Connected(0,3): " << ds.Connected(0,3) << "\n"; // 1
    std::cout << "Connected(0,4): " << ds.Connected(0,4) << "\n"; // 0
    std::cout << "Size(0): " << ds.Size(0) << "\n";               // 4
    std::cout << "Total sets: " << ds.Count() << "\n";            // 3

    ds.PrintSets();
    return 0;
}