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

並查集 Disjoint Set C 語言實現：路徑壓縮與按秩合併完整代碼

編輯：關於C語言

什麼是並查集？

並查集（Disjoint Set Union, DSU）維護一組**不相交集合**，支持兩大操作：

Find(x)：查找 x 所在集合的代表元（根節點）
Union(x, y)：合併 x、y 所在集合

應用：圖連通分量、Kruskal 最小生成树、動態連通性、網格島嶼計數等。

核心優化技術

路徑壓縮：`find` 過程中將沿途節點直接掛到根節點，攤還 O(α(n))
按秩合併：將秩（樹高上界）小的樹合併到大的樹下，保證樹高 ≤ log n

完整 C 實現

#include 
#include 

#define MAX_N 10000

typedef struct {
    int parent[MAX_N];
    int rank[MAX_N]; // 樹高上界
} DisjointSet;

void ds_init(DisjointSet *ds, int n) {
    for (int i = 0; i < n; i++) {
        ds->parent[i] = i;
        ds->rank[i] = 0;
    }
}

// 遞歸路徑壓縮
int ds_find(DisjointSet *ds, int x) {
    if (ds->parent[x] != x)
        ds->parent[x] = ds_find(ds, ds->parent[x]);
    return ds->parent[x];
}

// 迭代版（避免棧溢出）
int ds_find_iter(DisjointSet *ds, int x) {
    int root = x;
    while (ds->parent[root] != root) root = ds->parent[root];
    while (ds->parent[x] != x) {
        int p = ds->parent[x];
        ds->parent[x] = root;
        x = p;
    }
    return root;
}

void ds_union(DisjointSet *ds, int x, int y) {
    int rx = ds_find(ds, x);
    int ry = ds_find(ds, y);
    if (rx == ry) return;
    if (ds->rank[rx] < ds->rank[ry])
        ds->parent[rx] = ry;
    else if (ds->rank[rx] > ds->rank[ry])
        ds->parent[ry] = rx;
    else {
        ds->parent[ry] = rx;
        ds->rank[rx]++;
    }
}

int ds_same(DisjointSet *ds, int x, int y) {
    return ds_find(ds, x) == ds_find(ds, y);
}

// 測試主程序
int main() {
    DisjointSet ds;
    ds_init(&ds, 10);
    ds_union(&ds, 0, 1);
    ds_union(&ds, 1, 2);
    ds_union(&ds, 3, 4);
    printf("0 和 2 同集合？%d\n", ds_same(&ds, 0, 2)); // 1
    printf("0 和 3 同集合？%d\n", ds_same(&ds, 0, 3)); // 0
    ds_union(&ds, 2, 3);
    printf("合併後 0 和 4 同集合？%d\n", ds_same(&ds, 0, 4)); // 1
    return 0;
}

複雜度分析

**時間**：O(α(n)) ≈ O(1)，α 為阿克曼函數反函數，極慢增長
**空間**：O(n)
比 O(log n) 更快，實際中視為常數

常見變體與應用

變體	修改點	應用
帶權並查集	parent 存到根的距離/權值	食物鏈、模塊方程
可持久化並查集	函數式數據結構/主席樹	歷史版本查詢
並查集撤銷	記錄操作棧，支持回滾	離線動態連通性