並查集 (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）
• 同集合判斷：頂頭上司相同即為同一集合

最佳化策略#

樸素並查集在最壞情況下會退化成一條鏈，find 變成 O(N)。兩個經典最佳化把它壓回接近常數：

路徑壓縮 (Path Compression)#

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

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

按秩合併 (Union by Rank)#

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

兩者搭配可把均攤複雜度壓到 O(α(n))。實務上路徑壓縮效果已相當顯著，只用路徑壓縮往往就夠；下面的實作把兩者都寫進去以求完整。

程式碼實作#

class UnionFind(n: Int) {
    // 初始化：每個人的老大是自己
    private val parent = IntArray(n) { it }
    private val rank = IntArray(n)   // 樹高的上界，用於按秩合併

    // 查詢 + 路徑壓縮
    fun find(x: Int): Int {
        var root = x
        while (parent[root] != root) {
            root = parent[root]
        }
        // 路徑壓縮：把沿途節點直接指向 root
        var i = x
        while (i != root) {
            val next = parent[i]
            parent[i] = root
            i = next
        }
        return root
    }

    // 合併：按秩合併，矮樹掛到高樹下
    fun union(p: Int, q: Int) {
        val rootP = find(p)
        val rootQ = find(q)
        if (rootP == rootQ) return
        when {
            rank[rootP] < rank[rootQ] -> parent[rootP] = rootQ
            rank[rootP] > rank[rootQ] -> parent[rootQ] = rootP
            else -> {
                parent[rootQ] = rootP
                rank[rootP]++
            }
        }
    }

    // 判斷連通性
    fun connected(p: Int, q: Int): Boolean = find(p) == find(q)
}

複雜度分析#

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

應用場景#

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