併查集

問「這兩個在不在同一組」，幾乎是 O(1)。 · ⏱ 約 35 分鐘

你會學到三件事

1. 每一組選一個代表，問同組就是問代表一不一樣
2. 路徑壓縮：問過的順手接到代表上
3. 它為什麼只有十行，而快到幾乎是常數

開始之前

題目：n 個人，陸續告訴你「A 和 B 是朋友」， 隨時要能回答「X 和 Y 在不在同一群」。

用 BFS 的話每問一次要 O(n + 邊)。問 10⁵ 次就爆了。

🟢 先把編輯器打開，跟著下面一起做：跟著做

一、每組選一個代表

一開始每一個都是自己那一組的代表：

1vector<int> p(5);2for (int i = 0; i < 5; i++) p[i] = i;    // 一開始各自是自己的代表

p[x] 是「x 的上一層是誰」。一直往上找，找到自己指向自己的就是代表。

   2          代表是 2
   ↑
   1          p[1] = 2
   ↑
   0          p[0] = 1

二、find：往上找代表

一路往上問，直到問到代表自己：

1int find(vector<int>& p, int x) {2    if (p[x] == x) return x;          // 自己就是代表3    p[x] = find(p, p[x]);             // 🔴 路徑壓縮4    return p[x];5}

⚠️ 第三行那個賦值就是全部的關鍵。

沒有它的話，鏈可能長到 O(n)，每次 find 都要爬一遍。

有了它，這一次爬過的每一個點，都直接接到代表上：

爬之前          爬之後
   2               2
   ↑             ↗ ↑ ↖
   1            0  1  ...     ← 全部變成一層
   ↑
   0

問過一次，之後就近了。這叫路徑壓縮。

三、合併就是「讓一個代表指向另一個」

合併兩組只要一行：

1p[find(p, 1)] = find(p, 2);

讀法：「把 1 的代表指向 2 的代表」。

⚠️ 一定要寫 p[find(1)] = find(2)，不能寫 p[1] = 2。

寫成 p[1] = 2 的話，1 原本那一整群的其他人還指著舊的代表， 於是一群人被切成兩半，而程式不會報錯。

四、問同不同組

同不同組，就是問代表一不一樣：

1cout << (find(p, 1) == find(p, 2)) << endl;      // 1  ← 同組2cout << (find(p, 1) == find(p, 3)) << endl;      // 0  ← 不同組

代表一樣就是同一組，就這樣。

五、它有多快

加上路徑壓縮之後，均攤複雜度是 O(α(n))。 α 是反阿克曼函數，而在所有實際的 n 底下它都小於 5。

實務上就當它是 O(1)。

十行程式碼，換掉一個 O(n) 的查詢——這是競賽裡 CP 值最高的資料結構之一。

（還有一個「按秩合併」的優化，而只做路徑壓縮通常就夠快了。）

六、它能做什麼

完成的樣子

1#include <iostream>2#include <vector>3using namespace std;4int find(vector<int>& p, int x) {5    if (p[x] == x) return x;6    p[x] = find(p, p[x]);7    return p[x];8}9 10int main() {11    vector<int> p(5);12    for (int i = 0; i < 5; i++) p[i] = i;13    p[find(p, 1)] = find(p, 2);14    cout << (find(p, 1) == find(p, 2)) << endl;15    cout << (find(p, 1) == find(p, 3)) << endl;16    return 0;17}

換你了

把 p[x] = find(p, p[x]); 那一行改成 return find(p, p[x]); ——拿掉路徑壓縮。

小的資料看不出差別，而那正是它可怕的地方： 一個少了一行的版本，樣例全過，而大資料超時。

到編輯器做這一題：練習：拿掉路徑壓縮——而小資料【看不出差別】

做一個

七個人（0 到 6），關係是 0-1、1-2、3-4、5-6。印出總共分成幾群。

🔴 數群數不用另外記：代表就是自己的那些人，一個人算一群。 ⚠️ 而 0-1 和 1-2 合起來是一群三個人，不是兩群。

到編輯器做這一題：做一個：有幾群

這一課你做了什麼

• 你用「代表」表示了分組
• 你寫了帶路徑壓縮的 find
• 你知道合併要接代表，不是接元素

如果卡住了