不相交集 (Union-Find) 數據結構 C 實現：路徑壓縮、按秩合併、完整測試與應用場景

核心 ADT 設計

// uf.h
#ifndef UF_H
#define UF_H

typedef struct UF *UF;

UF uf_create(int n);           // 創建 n 個單元素集合 (0..n-1)
void uf_destroy(UF uf);
int uf_find(UF uf, int x);     // 查找根節點 (帶路徑壓縮)
void uf_union(UF uf, int a, int b); // 合併兩集合 (按秩)
int uf_connected(UF uf, int a, int b); // 判斷連通
int uf_count(UF uf);           // 當前集合數
int uf_size(UF uf, int x);     // x 所在集合大小 (可選)

#endif

高性能實現 (uf.c)

#include "uf.h"
#include 
#include 

struct UF {
    int *parent;   // 父節點，根節點 parent[x] = x
    int *rank;     // 秩 (樹高上界)
    int *size;     // 集合大小 (僅根節點有效)
    int count;     // 集合數
    int n;         // 元素總數
};

UF uf_create(int n) {
    if (n <= 0) return NULL;
    UF uf = malloc(sizeof(*uf));
    if (!uf) return NULL;
    uf->parent = malloc(n * sizeof(int));
    uf->rank = malloc(n * sizeof(int));
    uf->size = malloc(n * sizeof(int));
    if (!uf->parent || !uf->rank || !uf->size) {
        free(uf->parent); free(uf->rank); free(uf->size); free(uf);
        return NULL;
    }
    for (int i = 0; i < n; ++i) {
        uf->parent[i] = i;
        uf->rank[i] = 0;
        uf->size[i] = 1;
    }
    uf->count = n;
    uf->n = n;
    return uf;
}

void uf_destroy(UF uf) {
    if (uf) {
        free(uf->parent);
        free(uf->rank);
        free(uf->size);
        free(uf);
    }
}

/* 路徑壓縮：遞歸或迭代雙路徑 */
int uf_find(UF uf, int x) {
    if (x < 0 || x >= uf->n) return -1;
    int root = x;
    while (uf->parent[root] != root) root = uf->parent[root];
    // 路徑壓縮 (雙路徑)
    while (uf->parent[x] != root) {
        int next = uf->parent[x];
        uf->parent[x] = root;
        x = next;
    }
    return root;
}

/* 按秩合併 */
void uf_union(UF uf, int a, int b) {
    int ra = uf_find(uf, a);
    int rb = uf_find(uf, b);
    if (ra == rb || ra == -1 || rb == -1) return;
    // 秩小掛靠秩大
    if (uf->rank[ra] < uf->rank[rb]) {
        uf->parent[ra] = rb;
        uf->size[rb] += uf->size[ra];
    } else if (uf->rank[ra] > uf->rank[rb]) {
        uf->parent[rb] = ra;
        uf->size[ra] += uf->size[rb];
    } else {
        uf->parent[rb] = ra;
        uf->rank[ra]++;
        uf->size[ra] += uf->size[rb];
    }
    uf->count--;
}

int uf_connected(UF uf, int a, int b) {
    return uf_find(uf, a) == uf_find(uf, b);
}

int uf_count(UF uf) { return uf ? uf->count : 0; }
int uf_size(UF uf, int x) {
    int r = uf_find(uf, x);
    return (r == -1) ? 0 : uf->size[r];
}

複雜度分析

空間：O(n) 三個整型數組。

測試驗證 (test_uf.c)

#include "uf.h"
#include 
#include 

int main() {
    UF uf = uf_create(10);
    assert(uf_count(uf) == 10);
    
    uf_union(uf, 0, 1);
    uf_union(uf, 2, 3);
    uf_union(uf, 1, 2); // 0-1-2-3 連通
    assert(uf_connected(uf, 0, 3));
    assert(uf_size(uf, 0) == 4);
    assert(uf_count(uf) == 7); // 10 - 3
    
    uf_union(uf, 4, 5);
    uf_union(uf, 6, 7);
    uf_union(uf, 8, 9);
    assert(uf_count(uf) == 4);
    
    // 測試路徑壓縮效果
    for (int i = 0; i < 10; ++i) uf_find(uf, i);
    for (int i = 0; i < 10; ++i) assert(uf->parent[i] == uf_find(uf, i)); // 所有節點直指根
    
    uf_destroy(uf);
    printf("All tests passed.\n");
    return 0;
}

Makefile

CC = gcc
CFLAGS = -Wall -Wextra -O2 -std=c99

all: test_uf

test_uf: test_uf.o uf.o
	$(CC) -o $@ $^

%.o: %.c
	$(CC) $(CFLAGS) -c $< -o $@

clean:
	rm -f *.o test_uf

經典應用場景

1. Kruskal 最小生成樹：邊排序後，uf_connected 判環，uf_union 合併。
2. 動態連通性：網絡連接、社交圈子、圖像連通區域標記。
3. 離線查詢 (Tarjan 離線 LCA)：DFS 過程中維護祖先集合。
4. 網格滲流模型：N×N 網格隨機打開，判斷頂底連通。
5. 編譯器符號表合併：作用域嵌套時的符號合併。
6. 內存分配器 Buddy System 合併空閒塊：相鄰空閒塊合併。

進階優化

• 路徑分裂 / 路徑減半：while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } (單路徑，常數因子更小)。
• 按大小合併：用 size 代替 rank，邏輯更直觀，複雜度相同。
• 持久化并查集：函數式數據結構，支持歷史版本查詢 (主席樹/線段樹實現)。
• 並行并查集：CAS 原子操作實現無鎖 find/union (論文: "Wait-Free Parallel Algorithms for the Union-Find Problem")。

總結

不相交集是近乎常數時間解決動態連通性問題的神級數據結構。掌握路徑壓縮 (雙路徑/分裂/減半)、按秩/按大小合併、三數組佈局 (parent/rank/size)、邊界檢查、測試驗證，即可在競賽、系統開發、圖算法中自信使用。模板代碼建議收入個人庫，命名規範 uf_*，隨用隨取。