並查集 (Union-Find)#

並查集，又稱不交集資料結構 (Disjoint-Set)，用於處理集合的合併 (Union) 與查詢 (Find) 問題。

核心概念：幫派模型#

flowchart TB
    subgraph 初始狀態["初始狀態：每人都是自己的老大"]
        A1((A))
        B1((B))
        C1((C))
        D1((D))
    end

    subgraph 合併後["Union(A,B) + Union(C,D) + Union(B,C)"]
        A2((A)) --> B2((B))
        C2((C)) --> B2
        D2((D)) --> C2
    end

    subgraph 路徑壓縮["路徑壓縮後"]
        A3((A)) --> R((B))
        C3((C)) --> R
        D3((D)) --> R
    end

    style R fill:#e8f5e9

將並查集想像為「幫派組織」：

• 初始狀態：每個人都是自己的老大 (parent[i] = i)
• 查詢 (Find)：追溯「老大的老大」直到找到龍頭老大 (Root)
• 合併 (Union)：讓一方的老大拜另一方為老大

直觀理解

• parent[x]：x 的直屬上級
• root：龍頭老大（parent[root] == root）
• 同集合判斷：頂頭上司相同即為同一集合

優化策略#

路徑壓縮 (Path Compression)#

在 find 過程中，將路徑上所有節點直接指向 Root，使後續查詢接近 O(1)。

原本：D -> C -> B -> A (root)
壓縮後：D -> A, C -> A, B -> A

按秩合併 (Union by Rank)#

將深度較小的樹合併到深度較大的樹下，避免樹高度無謂增長。

實務上路徑壓縮效果顯著，通常使用路徑壓縮後可省略按秩合併。

程式碼實作#

class UnionFind {
    private int[] roots;

    // 初始化：每個人的老大是自己
    public UnionFind(int n) {
        roots = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
    }

    // 查詢 + 路徑壓縮
    public int find(int i) {
        int root = i;
        while (roots[root] != root) {
            root = roots[root];
        }
        // 路徑壓縮
        while (i != roots[i]) {
            int temp = roots[i];
            roots[i] = root;
            i = temp;
        }
        return root;
    }

    // 合併
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP != rootQ) {
            roots[rootP] = rootQ;
        }
    }

    // 判斷連通性
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }
}

複雜度分析#

使用路徑壓縮後，並查集的各項操作均攤時間複雜度為 O(α(n))，其中 α 為反阿克曼函式，實際可視為常數。

應用場景#

• 社交網路：判斷兩人是否在同一社交圈
• 區塊鏈：維護比特幣網路節點連通性
• 圖論：判斷圖的連通分量（如島嶼數量問題）