Disjoint Set（並查集 / UnionFind）演算法完整教學

Disjoint Set 簡介與動機
基本術語與資料結構
三大基本操作
實作 1：Quick Find（陣列直接記錄群編號）
實作 2：Quick Union（樹狀父節點表示）
優化 1：Union by Size / Union by Rank
優化 2：Path Compression（路徑壓縮）
兩種優化結合：近乎常數時間
完整推演範例
攤還分析（Amortized Analysis）
複雜度總表
常見變形與進階技巧
實際應用
C++ 完整實作
應用範例：Kruskal MST、連通分量、環偵測
程式碼參照

1. Disjoint Set 簡介與動機

Disjoint Set（不相交集合），又稱 Union-Find 或 並查集，是一種維護「互不相交集合的動態分組（partition）」的資料結構。

核心問題

假設有 (N) 個元素 {0, 1, 2, ..., N-1}，一開始每個元素自成一個集合。我們需要支援以下兩種操作：

Union(x, y)：合併 x 所在的集合與 y 所在的集合
Find(x)：詢問 x 屬於哪個集合（傳回該集合的代表 / 領袖 / leader）

並由 Find 衍生出：

Connected(x, y) 或 SameSet(x, y)：判斷 x 與 y 是否在同一集合（即 Find(x) == Find(y)）

為什麼需要它？

動態連通性查詢：邊一條一條加進來，隨時想知道兩個節點是否連通
最小生成樹（Kruskal 演算法）：每加一條邊都要判斷是否形成環
影像處理：相連像素區塊（Connected Component Labeling）
離線查詢：處理一連串 Union / Query 混合輸入
網路 / 社群分析：朋友的朋友也是朋友（傳遞閉包）

為什麼不直接用 Graph + BFS/DFS？

方法	Union 成本	Connected 查詢成本
Graph + BFS/DFS	O(1) 加邊	O(N + E) 每次查詢
Disjoint Set	近乎 O(1)	近乎 O(1)

Disjoint Set 在「只關心是否連通，不需要實際路徑」的場景下，速度遠優於圖論做法。

2. 基本術語與資料結構

2.1 表示法：森林（Forest of Trees）

每個集合用一棵樹表示，樹的 根節點 是該集合的 代表（representative）。

集合 {0, 1, 2, 3}        集合 {4, 5}        集合 {6}
     0 (root)                4 (root)          6 (root)
    /|\                      |
   1 2 3                     5

每個元素只記錄一件事：自己的 parent 是誰。

2.2 核心陣列

parent[i]   = 元素 i 的父節點
parent[i] == i  ⇔  i 是 root（自己是自己的父親）

用「自指」表示根節點，是 Union-Find 最簡潔的設計。

2.3 額外輔助陣列（優化用）

size[i]   = 以 i 為 root 的子樹大小（Union by Size 用）
rank[i]   = 以 i 為 root 的子樹「秩」 ≈ 樹高上界（Union by Rank 用）

Size 與 Rank 通常只在 root 處有意義，非 root 的值不會被讀取。

3. 三大基本操作

3.1 MakeSet（初始化）

為每個元素建立一個只含自己的集合。

MakeSet(N):
    for i = 0 to N-1:
        parent[i] = i
        size[i]   = 1
        rank[i]   = 0

時間：O(N)

3.2 Find(x)

回傳 x 所在集合的代表（root）。

Find(x):
    while parent[x] != x:
        x = parent[x]
    return x

時間：O(樹高)，最壞 O(N)，加上路徑壓縮後接近 O(1)。

3.3 Union(x, y)

合併 x 和 y 所在的集合。

Union(x, y):
    rx = Find(x)
    ry = Find(y)
    if rx == ry: return        # 已在同一集合
    parent[rx] = ry            # 直接掛上去（未優化）

時間：O(Find)

⚠️ 沒有優化的「直接掛」可能讓樹退化成一條鏈，導致 Find 變 O(N)。

4. 實作 1：Quick Find（陣列直接記錄群編號）

最直觀的做法：用一維陣列 id[i] 直接存「i 屬於哪個群」。

操作

Find(x)        : return id[x]                        # O(1)
Connected(x,y) : return id[x] == id[y]               # O(1)
Union(x,y)     :
    a = id[x]
    b = id[y]
    if a == b: return
    for i = 0 to N-1:
        if id[i] == a: id[i] = b                     # O(N)

評價

操作	複雜度
Find	O(1)
Union	O(N)

問題： Union 慢。M 次 Union 是 O(MN)，N=10⁶ 時根本不能用。

通常只在「Find 極度頻繁、Union 極少」時才考慮。

5. 實作 2：Quick Union（樹狀父節點表示）

改用森林：每個集合一棵樹，parent[i] 指向父節點。

操作

Find(x):
    while parent[x] != x:
        x = parent[x]
    return x

Union(x, y):
    rx = Find(x)
    ry = Find(y)
    if rx == ry: return
    parent[rx] = ry

圖示

初始：              Union(1,2):           Union(3,4):           Union(2,4):
0 1 2 3 4              0   2 3 4              0   2 4              0   4
                          /                      / /                  /
                         1                      1 3                  2
                                                                    /
                                                                   1
                                                                   ...

最終 Union(0, 1):
                                                                    4
                                                                    |
                                                                    2
                                                                   /|\
                                                                  1 0 ?

實際合併 root 即可：parent[0] = 4

評價

操作	最壞複雜度
Find	O(N)（樹退化成鏈）
Union	O(N)

看似有改進，但若一直把大樹掛在小樹上，仍可能退化。需要進一步優化。

6. 優化 1：Union by Size / Union by Rank

核心想法： 合併時，讓較小（或較矮）的樹掛到較大（或較高）的樹之下，避免樹高無謂增長。

6.1 Union by Size（依大小合併）

size[r] = 以 r 為 root 的樹大小。

Union(x, y):
    rx = Find(x); ry = Find(y)
    if rx == ry: return
    if size[rx] < size[ry]:
        parent[rx] = ry
        size[ry] += size[rx]
    else:
        parent[ry] = rx
        size[rx] += size[ry]

6.2 Union by Rank（依秩合併）

rank[r] = 以 r 為 root 的子樹「秩」（≈ 樹高上界，不一定等於實際高度）。

Union(x, y):
    rx = Find(x); ry = Find(y)
    if rx == ry: return
    if rank[rx] < rank[ry]:
        parent[rx] = ry
    elif rank[rx] > rank[ry]:
        parent[ry] = rx
    else:
        parent[ry] = rx
        rank[rx]  += 1                  # 同秩 → 合併後 root 秩 +1

6.3 為何有效？

定理： Union by Size / Rank 後，任何樹的高度 ≤ ⌊log₂ N⌋。

直覺證明（Size 版）：

當大小為 (s_1) 的樹被掛到大小為 (s_2 \geq s_1) 的樹下時，其中元素的「深度」最多 +1。每次 +1，元素所在樹的大小至少加倍。深度加 (k) 次代表大小至少 (2^k)，所以 (2^k \leq N)，即 (k \leq \log_2 N)。

6.4 改進後的複雜度

操作	複雜度
Find	O(log N)
Union	O(log N)

7. 優化 2：Path Compression（路徑壓縮）

核心想法： Find 的時候，順便把走過的所有節點都直接接到 root 上，下次 Find 就快了。

7.1 遞迴版（最常見）

Find(x):
    if parent[x] != x:
        parent[x] = Find(parent[x])     # 把 x 直接接到 root
    return parent[x]

7.2 迭代版（兩段式）

Find(x):
    # 第一段：找到 root
    r = x
    while parent[r] != r:
        r = parent[r]
    # 第二段：把路徑上每個節點都直接接到 root
    while parent[x] != r:
        next = parent[x]
        parent[x] = r
        x = next
    return r

7.3 Path Halving（路徑減半）— 簡化版

Find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   # 隔一個就接到祖父
        x = parent[x]
    return x

Path Halving 不需要遞迴或第二回合掃描，常數最小、實作簡單，效果與完整路徑壓縮幾乎相同。

7.4 圖示

壓縮前 Find(7):                   壓縮後 Find(7):
        1                                   1
       /                                  /|\|\
      2                                  2 3 5 7
     /                                   |
    3                                    4
   /                                    （6 的父親被改）
  4
 /
5
/
6
/
7

7.5 單獨用 Path Compression 的複雜度

操作	攤還複雜度
Find	O(log N) 攤還（單次仍可能 O(N)）

8. 兩種優化結合：近乎常數時間

同時使用 Union by Rank（或 Size）+ Path Compression

8.1 結果

操作	攤還複雜度
Find	O(α(N))
Union	O(α(N))

其中 (\alpha(N)) 是 反阿克曼函數（Inverse Ackermann function）。

8.2 反阿克曼函數有多小？

[ \alpha(N) \leq 4 \text{，對所有 } N \leq 2^{2^{2^{2^{16}}}} ]

也就是說，對於任何實際可能的 N（甚至宇宙原子數），(\alpha(N) \leq 4)，可以視為 常數時間。

Tarjan (1975) 證明： 用了「Union by Rank + Path Compression」後，(m) 次操作的總成本是 O(m · α(N))，且這個界是緊的（無法再改進）。

8.3 為何這麼快？

Union by Rank：樹高被限制在 (O(\log N))
Path Compression：每做一次 Find，路徑變短，往後幾乎免費
兩者合作，攤還下每個操作只需「剝幾層阿克曼函數」的時間

9. 完整推演範例

設 N = 10。我們做以下操作：

Union(0, 1)
Union(2, 3)
Union(4, 5)
Union(6, 7)
Union(0, 2)
Union(4, 6)
Union(0, 4)
Find(7)

採用 Union by Rank + Path Compression。

步驟 1: 初始

i:        0 1 2 3 4 5 6 7 8 9
parent:   0 1 2 3 4 5 6 7 8 9
rank:     0 0 0 0 0 0 0 0 0 0

步驟 2: Union(0, 1)（rank 相同）

parent[1] = 0; rank[0] = 1

森林:
0   2   3   4   5   6   7   8   9
|
1

步驟 3: Union(2, 3)、Union(4, 5)、Union(6, 7)（同樣的形狀）

0   2   4   6   8   9
|   |   |   |
1   3   5   7

rank: [1,0,1,0,1,0,1,0,0,0]

步驟 4: Union(0, 2)（rank 相同 → 0 變 root，rank[0] = 2）

        0
       /|
      1 2
        |
        3

rank: [2,0,1,0,1,0,1,0,0,0]

步驟 5: Union(4, 6)（rank 相同 → 4 變 root，rank[4] = 2）

0:           4:                8   9
   0           4
  /|          /|
 1 2         5 6
   |           |
   3           7

步驟 6: Union(0, 4)（rank 相同 → 0 變 root，rank[0] = 3）

            0
        ___/|\___
       /  / |   \
      1  2  4    (1 是直接子，2 也是)
         |  /|
         3 5 6
              |
              7

i	0	1	2	3	4	5	6	7
parent	0	0	0	2	0	4	4	6
rank	3	0	1	0	2	0	1	0

步驟 7: Find(7) — Path Compression

路徑：7 → 6 → 4 → 0
找到 root = 0 後，把 7、6、4 都直接接到 0：

壓縮前:                 壓縮後:
       0                       0
      /|\                    / | | | \
     1 2 4                  1  2 4 6  7
       | /|                    |
       3 5 6                   3
            |                  (5 仍掛 4，因為沒走過)
            7

i	0	1	2	3	4	5	6	7
parent	0	0	0	2	0	4	0	0
rank	3	0	1	0	2	0	1	0

注意：rank 不需更新（rank 只是上界，不是實際高度）。

10. 攤還分析（Amortized Analysis）

10.1 為什麼是 (O(\alpha(N)))？

完整證明非常技術性（Tarjan 1975），這裡只給直覺。

10.2 位能函數（Potential Function）

定義每個節點的「等級（level）」與「索引（index）」，並令位能：

[ \Phi(F) = \sum_{x \in F} \phi(x) ]

其中 (\phi(x)) 與 (x) 在森林中的位置相關。

10.3 關鍵性質

Union by Rank 保證樹高 ≤ (\log_2 N)
Path Compression 保證任意節點被「碰到」一次後，下次拜訪近乎免費
兩者結合 → 任意 (m) 次操作的總成本是 O((m + n) · α(n))

10.4 下界

Fredman & Saks (1989)：在 cell-probe model 下，任何只用指標的 Union-Find 結構，(m) 次操作至少需要 (\Omega(m \cdot \alpha(n))) 時間。

也就是說，「Union by Rank + Path Compression」已經是最優演算法！

11. 複雜度總表

實作	MakeSet	Find	Union	空間
Quick Find	O(N)	O(1)	O(N)	O(N)
Quick Union	O(N)	O(N)	O(N)	O(N)
+ Union by Size/Rank	O(N)	O(log N)	O(log N)	O(N)
+ Path Compression	O(N)	O(log N) 攤還	O(log N) 攤還	O(N)
+ 兩者合用	O(N)	O(α(N)) ≈ O(1)	O(α(N)) ≈ O(1)	O(N)

12. 常見變形與進階技巧

12.1 帶權並查集（Weighted Union-Find）

額外維護「x 到 root 的權重關係」，可解決「相對距離 / 比例」問題。

parent[x], weight[x]   // weight[x] = x 到 parent[x] 的距離

例題：給定 relation(a, b, w) 表示 (a - b = w)，回答任意 query(a, b) 的差值。

12.2 啟發式合併（Small-to-Large）

在某些變形（例如「離線維護集合所屬資訊」）中，合併兩個集合時把小的全部搬到大的，總成本 O(N log N)。

12.3 可撤銷並查集（Rollback Union-Find）

不使用 Path Compression（保留原本的樹結構），用 Stack 記錄每次 Union 的修改，可在 O(log N) 內回退（用於分治、線段樹分治、離線動態圖連通性）。

12.4 持久化並查集（Persistent Union-Find）

用持久化陣列（Persistent Array）實作，可保留每個版本，支援版本查詢。

12.5 種類並查集（Bipartite / k-Color）

把每個節點拆成 k 份來表示「敵人 / 朋友 / 同類 / 不同類」等多種關係。

13. 實際應用

應用	說明
Kruskal MST	排序邊後，依序加入，用 Union-Find 判斷是否形成環
連通分量數	動態加邊，隨時知道有幾個連通塊
離線動態連通性	處理 add/query 混合序列
影像處理	Connected Component Labeling（區塊標記）
網路 / 社群	朋友群分析、推薦系統的相似度群
編譯器 / Type Inference	Hindley-Milner 型別推論的型別合一（unification）
遊戲 / 物理引擎	剛體連接、碰撞群組
Percolation 模擬	滲流模型、統計物理
LCA（Tarjan 離線演算法）	用 Union-Find 加 DFS 求最近公共祖先

14. C++ 完整實作

14.1 基本版（Quick Union，未優化，教學用）

#include <vector>

class UnionFindBasic {
public:
    UnionFindBasic(int n) : parent(n) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }

    int find(int x) {
        while (parent[x] != x) x = parent[x];
        return x;
    }

    void unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return;
        parent[rx] = ry;
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }

private:
    std::vector<int> parent;
};

14.2 Union by Rank + Path Compression（推薦使用）

#include <vector>
#include <numeric>

class UnionFind {
public:
    explicit UnionFind(int n)
        : parent(n), rnk(n, 0), sz(n, 1), components(n) {
        std::iota(parent.begin(), parent.end(), 0);
    }

    // Path Compression（遞迴版）
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    // Union by Rank
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;        // 已在同一集合

        if (rnk[rx] < rnk[ry]) std::swap(rx, ry);
        // 現在 rnk[rx] >= rnk[ry]，把 ry 掛到 rx 之下
        parent[ry] = rx;
        sz[rx] += sz[ry];
        if (rnk[rx] == rnk[ry]) ++rnk[rx];

        --components;
        return true;
    }

    bool connected(int x, int y) { return find(x) == find(y); }
    int  size(int x)             { return sz[find(x)]; }
    int  count() const           { return components; }   // 目前集合數

private:
    std::vector<int> parent;
    std::vector<int> rnk;            // 秩（樹高上界）
    std::vector<int> sz;             // 集合大小（root 處有效）
    int              components;     // 連通塊數
};

14.3 Path Halving 迭代版（無遞迴、最快）

int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];   // 隔一級往上接
        x = parent[x];
    }
    return x;
}

在效能敏感場景（如競賽、大型圖演算法）中，Path Halving + Union by Rank 是常見最佳組合。

14.4 完整可執行範例（含 main）

#include <iostream>
#include <vector>
#include <numeric>

class UnionFind {
public:
    explicit UnionFind(int n)
        : parent(n), rnk(n, 0), sz(n, 1), components(n) {
        std::iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        // Path Halving
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rnk[rx] < rnk[ry]) std::swap(rx, ry);
        parent[ry] = rx;
        sz[rx] += sz[ry];
        if (rnk[rx] == rnk[ry]) ++rnk[rx];
        --components;
        return true;
    }

    bool connected(int x, int y) { return find(x) == find(y); }
    int  size(int x)             { return sz[find(x)]; }
    int  count() const           { return components; }

private:
    std::vector<int> parent, rnk, sz;
    int              components;
};

int main() {
    UnionFind uf(10);

    uf.unite(0, 1);
    uf.unite(2, 3);
    uf.unite(4, 5);
    uf.unite(6, 7);
    uf.unite(0, 2);
    uf.unite(4, 6);
    uf.unite(0, 4);

    std::cout << "components = " << uf.count()           << '\n';   // 4
    std::cout << "connected(1, 7) = " << uf.connected(1, 7) << '\n'; // 1
    std::cout << "connected(1, 8) = " << uf.connected(1, 8) << '\n'; // 0
    std::cout << "size of group containing 3 = " << uf.size(3) << '\n'; // 8
    return 0;
}

14.5 可撤銷並查集（Rollback Union-Find）

不做 Path Compression，改用 stack 記錄每次 unite 的修改。

#include <vector>
#include <stack>
#include <numeric>

class RollbackUF {
public:
    explicit RollbackUF(int n) : parent(n), sz(n, 1) {
        std::iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) const {                     // 不壓縮，純走 parent
        while (parent[x] != x) x = parent[x];
        return x;
    }

    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) {
            history.push({-1, -1, -1, -1});      // 占位，方便 rollback
            return false;
        }
        if (sz[rx] < sz[ry]) std::swap(rx, ry);
        history.push({ry, parent[ry], rx, sz[rx]});
        parent[ry] = rx;
        sz[rx] += sz[ry];
        return true;
    }

    void rollback() {
        if (history.empty()) return;
        auto [a, pa, b, sb] = history.top();
        history.pop();
        if (a == -1) return;                     // 占位
        parent[a] = pa;
        sz[b]     = sb;
    }

private:
    struct Op { int a, parentA, b, sizeB; };
    std::vector<int>  parent, sz;
    std::stack<Op>    history;
};

15. 應用範例：Kruskal MST、連通分量、環偵測

15.1 Kruskal 最小生成樹

#include <algorithm>
#include <vector>

struct Edge { int u, v, w; };

long long kruskalMST(int n, std::vector<Edge>& edges) {
    std::sort(edges.begin(), edges.end(),
              [](const Edge& a, const Edge& b){ return a.w < b.w; });

    UnionFind uf(n);
    long long total = 0;
    int       used  = 0;

    for (const auto& e : edges) {
        if (uf.unite(e.u, e.v)) {        // 不形成環才加入
            total += e.w;
            if (++used == n - 1) break;  // n-1 條邊就完成
        }
    }
    return (used == n - 1) ? total : -1; // -1 表示圖不連通
}

複雜度：O(E log E)（瓶頸在排序，Union-Find 部分近乎 O(E)）

15.2 連通分量計數

int countComponents(int n, const std::vector<std::pair<int,int>>& edges) {
    UnionFind uf(n);
    for (const auto& [u, v] : edges) uf.unite(u, v);
    return uf.count();
}

15.3 無向圖環偵測

bool hasCycle(int n, const std::vector<std::pair<int,int>>& edges) {
    UnionFind uf(n);
    for (const auto& [u, v] : edges) {
        if (!uf.unite(u, v)) return true;  // u, v 已連通 → 多這條邊就成環
    }
    return false;
}

15.4 動態加邊查詢（典型 Union-Find 題型）

Q 筆操作：
  "U a b"   → 合併
  "?  a b"  → 詢問是否同集合

#include <iostream>
int main() {
    int n, q; std::cin >> n >> q;
    UnionFind uf(n);
    while (q--) {
        char op; int a, b; std::cin >> op >> a >> b;
        if (op == 'U') uf.unite(a, b);
        else           std::cout << (uf.connected(a, b) ? "YES" : "NO") << '\n';
    }
}

16. 程式碼參照

下列檔案為對應的 C++ 範例（如尚未存在，可依本教材的 14.4 節即時建立 disjoint_set.cpp）：

檔案	內容
`disjoint_set.cpp`	Disjoint Set 完整實作：基本版、Rank+PathCompression 版、Rollback 版、應用範例

編譯與執行

g++ -std=c++17 -Wall -O2 -o disjoint_set disjoint_set.cpp
./disjoint_set

建議練習題

LeetCode 547. Number of Provinces — 計算連通分量
LeetCode 684. Redundant Connection — 找形成環的多餘邊
LeetCode 1319. Number of Operations to Make Network Connected
UVa 11503 Virtual Friends — 維護 friend 群大小
POJ 1182 食物鏈 — 種類並查集（3-color）
CSES Road Reparation / Road Construction — Kruskal 與動態連通分量

附錄 A：Union by Rank vs Union by Size 比較

項目	Union by Rank	Union by Size
維護量	rank（≈ 高度上界）	size（精確大小）
何時 root 改變	較矮的接到較高的	較小的接到較大的
額外資訊用途	只用於合併決策	合併決策 + 集合大小查詢
複雜度	同為 O(α(N))（攤還）	同為 O(α(N))（攤還）
實務建議	競賽常用（記憶體小）	需 size 查詢時用

兩者效率相同，多數實作會混用：用 size 做合併決策，同時 size 也對外提供「集合大小」查詢功能。

附錄 B：常見錯誤與陷阱

忘了路徑壓縮：在大規模測資下會 TLE。
Path Compression 寫成迴圈但忘記更新 parent：必須在迴圈中真正改寫 parent[x] = root，否則沒效果。
Union 沒先 Find：parent[x] = y 直接合併節點而非根，會破壞結構。
rank 寫成「實際高度」：Path Compression 後高度可能下降，但 rank 不需更新（它只是上界）。
size 在非 root 處取值：必須先 find(x) 找到 root 再讀 size。
多元素 0-index / 1-index 混用：建立 UnionFind(n+1) 並一律用 1-indexed，可避免錯誤。

參考文獻：

Tarjan, R. E. (1975). Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2), 215-225.
Tarjan, R. E., & van Leeuwen, J. (1984). Worst-case analysis of set union algorithms. Journal of the ACM, 31(2), 245-281.
Fredman, M., & Saks, M. (1989). The cell probe complexity of dynamic data structures. STOC.
CLRS, Introduction to Algorithms (3rd ed.), Chapter 21: Data Structures for Disjoint Sets.
Sedgewick & Wayne, Algorithms (4th ed.), Chapter 1.5: Case Study: Union-Find.

目錄

1. Disjoint Set 簡介與動機

核心問題

為什麼需要它？

為什麼不直接用 Graph + BFS/DFS？

2. 基本術語與資料結構

2.1 表示法：森林（Forest of Trees）

2.2 核心陣列

2.3 額外輔助陣列（優化用）

3. 三大基本操作

3.1 MakeSet（初始化）

3.2 Find(x)

3.3 Union(x, y)

4. 實作 1：Quick Find（陣列直接記錄群編號）

操作

評價

5. 實作 2：Quick Union（樹狀父節點表示）

操作

圖示

評價

6. 優化 1：Union by Size / Union by Rank

6.1 Union by Size（依大小合併）

6.2 Union by Rank（依秩合併）

6.3 為何有效？

6.4 改進後的複雜度

7. 優化 2：Path Compression（路徑壓縮）

7.1 遞迴版（最常見）

7.2 迭代版（兩段式）

7.3 Path Halving（路徑減半）— 簡化版

7.4 圖示

7.5 單獨用 Path Compression 的複雜度

8. 兩種優化結合：近乎常數時間

8.1 結果

8.2 反阿克曼函數有多小？

8.3 為何這麼快？

9. 完整推演範例

步驟 1: 初始

步驟 2: Union(0, 1)（rank 相同）

步驟 3: Union(2, 3)、Union(4, 5)、Union(6, 7)（同樣的形狀）

步驟 4: Union(0, 2)（rank 相同 → 0 變 root，rank[0] = 2）

步驟 5: Union(4, 6)（rank 相同 → 4 變 root，rank[4] = 2）

步驟 6: Union(0, 4)（rank 相同 → 0 變 root，rank[0] = 3）

步驟 7: Find(7) — Path Compression

10. 攤還分析（Amortized Analysis）

10.1 為什麼是 (O(\alpha(N)))？

10.2 位能函數（Potential Function）

10.3 關鍵性質

10.4 下界

11. 複雜度總表

12. 常見變形與進階技巧

12.1 帶權並查集（Weighted Union-Find）

12.2 啟發式合併（Small-to-Large）

12.3 可撤銷並查集（Rollback Union-Find）

12.4 持久化並查集（Persistent Union-Find）

12.5 種類並查集（Bipartite / k-Color）

13. 實際應用

14. C++ 完整實作

14.1 基本版（Quick Union，未優化，教學用）

14.2 Union by Rank + Path Compression（推薦使用）

14.3 Path Halving 迭代版（無遞迴、最快）

14.4 完整可執行範例（含 main）

14.5 可撤銷並查集（Rollback Union-Find）

15. 應用範例：Kruskal MST、連通分量、環偵測

15.1 Kruskal 最小生成樹

15.2 連通分量計數

15.3 無向圖環偵測

15.4 動態加邊查詢（典型 Union-Find 題型）

16. 程式碼參照

編譯與執行

建議練習題

附錄 A：Union by Rank vs Union by Size 比較

附錄 B：常見錯誤與陷阱

Articoli correlati

問題是什麼

問題是什麼

問題是什麼

問題是什麼

問題是什麼

問題是什麼