C++ 並查集 UFSet 類完整實現與效能比較

並查集資料結構介紹

並查集（Union-Find Set，簡稱 UFSet）是一種處理不相交集合合併與查詢問題的經典資料結構。它支援兩種核心操作：查找 以確定元素所屬集合的代表元（族長），以及 合併 將兩個集合合而為一。本文提供一個完整的 C++ 類別實現，包含基本版本與路徑壓縮、按秩合併（按大小合併）兩種優化策略，並附帶效能測試程式碼。

類別設計與核心介面

UFSet 類別封裝了並查集的所有操作，主要成員包括：

• father 陣列：儲存每個節點的父節點索引；負值表示該節點為根節點，且絕對值代表該集合大小。
• size：集合最大元素數量。

公開介面涵蓋建構函數、拷貝建構函數、指派運算子、析構函數，以及核心演算法函式：

• FindFather(int pos)：遞迴尋找根節點（基本版）。
• Unite(int posI, int posJ)：基本合併操作，直接將一棵樹掛在另一棵樹根下。
• FindFatherAndReducePath(int pos)：路徑壓縮 查找，將沿途節點直接指向根節點，大幅降低樹高。
• UnionBySize(int posI, int posJ)：按大小合併，將較小的樹合併到較大的樹下，配合路徑壓縮可達到近乎常數時間複雜度。
• SameFamily(int posI, int posJ)：判斷兩元素是否屬於同一集合。
• PrintUFSet()：除錯用，輸出內部陣列狀態。

關鍵演算法解析

基本查找與合併

int UFSet::FindFather(int pos) {
    if (father[pos] < 0) return pos;
    return FindFather(father[pos]);
}

bool UFSet::Unite(int posI, int posJ) {
    int fI = FindFather(posI), fJ = FindFather(posJ);
    if (fI == fJ) return false;
    father[fJ] = fI; // 簡單合併，不考慮樹高平衡
    return true;
}

路徑壓縮查找

int UFSet::FindFatherAndReducePath(int pos) {
    if (father[pos] < 0) return pos;
    return father[pos] = FindFatherAndReducePath(father[pos]); // 壓縮路徑
}

此寫法利用遞迴回溯時的賦值，將路徑上所有節點的父指標直接指向根節點，使後續查找極快。

按大小合併

bool UFSet::UnionBySize(int posI, int posJ) {
    int fI = FindFatherAndReducePath(posI);
    int fJ = FindFatherAndReducePath(posJ);
    if (fI == fJ) return false;
    // father[root] 儲存負的集合大小，故值越小代表集合越大
    if (father[fI] < father[fJ]) {
        father[fI] += father[fJ];
        father[fJ] = fI;
    } else {
        father[fJ] += father[fI];
        father[fI] = fJ;
    }
    return true;
}

合併時將元素較少的集合併入較大集合，配合路徑壓縮，時間複雜度可達 O(α(n))（反阿克曼函數），實際應用中幾乎為常數時間。

效能測試與比較

main() 函式分別對基本版 Unite 與優化版 UnionBySize 執行 50,000 次隨機合併操作，並計時比較。測試程式碼片段：

time(&startTime);
for (int i = 0; i < MAX; ++i) {
    p = rand() % MAX + 1;
    q = rand() % MAX + 1;
    if (p != q) obj.Unite(p, q); // 或 obj.UnionBySize(p, q);
}
// ... 驗證與計時輸出

實測結果顯示，優化版在大規模資料下速度顯著優於基本版，特別是當合併操作頻繁且查詢操作混合時，路徑壓縮與按大小合併的組合效果最為明顯。

完整原始碼

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

const int MAX = 50000;

class UFSet {
public:
    UFSet(int s = MAX);
    UFSet(const UFSet &obj);
    ~UFSet() { delete[] father; }
    UFSet &operator=(const UFSet &obj);
    int FindFather(int pos);
    bool Unite(int posI, int posJ);
    int FindFatherAndReducePath(int pos);
    bool UnionBySize(int posI, int posJ);
    bool SameFamily(int posI, int posJ);
    void PrintUFSet();
private:
    int *father;
    int size;
};

// 建構函數：初始化 father 陣列為 -1
UFSet::UFSet(int s) : size(s) {
    father = new int[size + 1];
    for (int i = 0; i <= size; ++i) father[i] = -1;
}

// 拷貝建構函數與指派運算子（深拷貝）
UFSet::UFSet(const UFSet &obj) : size(obj.size) {
    father = new int[size + 1];
    for (int i = 0; i <= size; ++i) father[i] = obj.father[i];
}
UFSet &UFSet::operator=(const UFSet &obj) {
    if (this == &obj) return *this;
    delete[] father;
    size = obj.size;
    father = new int[size + 1];
    for (int i = 0; i <= size; ++i) father[i] = obj.father[i];
    return *this;
}

// 基本查找
int UFSet::FindFather(int pos) {
    if (father[pos] < 0) return pos;
    return FindFather(father[pos]);
}

// 基本合併
bool UFSet::Unite(int posI, int posJ) {
    int fI = FindFather(posI), fJ = FindFather(posJ);
    if (fI == fJ) return false;
    father[fJ] = fI;
    return true;
}

// 路徑壓縮查找
int UFSet::FindFatherAndReducePath(int pos) {
    if (father[pos] < 0) return pos;
    return father[pos] = FindFatherAndReducePath(father[pos]);
}

// 按大小合併（配合路徑壓縮）
bool UFSet::UnionBySize(int posI, int posJ) {
    int fI = FindFatherAndReducePath(posI);
    int fJ = FindFatherAndReducePath(posJ);
    if (fI == fJ) return false;
    if (father[fI] < father[fJ]) {
        father[fI] += father[fJ];
        father[fJ] = fI;
    } else {
        father[fJ] += father[fI];
        father[fI] = fJ;
    }
    return true;
}

bool UFSet::SameFamily(int posI, int posJ) {
    return FindFatherAndReducePath(posI) == FindFatherAndReducePath(posJ);
}

void UFSet::PrintUFSet() {
    for (int i = 0; i <= size; ++i) cout << father[i] << ' ';
    cout << endl;
}

int main() {
    time_t startTime, endTime;
    UFSet obj;
    int p, q;

    // 測試基本版
    time(&startTime);
    for (int i = 0; i < MAX; ++i) {
        p = rand() % MAX + 1;
        q = rand() % MAX + 1;
        if (p != q) obj.Unite(p, q);
    }
    // 簡單驗證
    p = rand() % MAX + 1;
    q = rand() % MAX + 1;
    if (p != q) cout << (obj.SameFamily(p, q) ? "≡" : "!≡") << endl;
    time(&endTime);
    cout << "基本版耗時: " << difftime(endTime, startTime) << " 秒" << endl;

    // 測試優化版
    time(&startTime);
    for (int i = 0; i < MAX; ++i) {
        p = rand() % MAX + 1;
        q = rand() % MAX + 1;
        if (p != q) obj.UnionBySize(p, q);
    }
    p = rand() % MAX + 1;
    q = rand() % MAX + 1;
    if (p != q) cout << (obj.SameFamily(p, q) ? "≡" : "!≡") << endl;
    time(&endTime);
    cout << "優化版耗時: " << difftime(endTime, startTime) << " 秒" << endl;

    return 0;
}

總結與應用場景

並查集廣泛應用於：

• 圖論中的 Kruskal 最小生成樹演算法（檢測環路）。
• 動態連通性問題（如網路連線、社交圈層合併）。
• 圖像處理中的連通區域標記。
• 離線查詢問題（如 Tarjan 離線 LCA）。

掌握路徑壓縮與按秩合併兩大優化技巧，是高效實現並查集的關鍵。本文提供的 UFSet 類別結構清晰、介面完整，可直接整合至專案中使用。