併查集

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

你會學到三件事

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

開始之前

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

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

一、每組選一個代表

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

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

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

二、find：往上找代表

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

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

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

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

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

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

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

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

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

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

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

四、問同不同組

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

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

五、它有多快

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

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

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

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

六、它能做什麼

完成的樣子

int find(vector<int>& p, int x) {
    if (p[x] == x) return x;
    p[x] = find(p, p[x]);
    return p[x];
}

int main() {
    vector<int> p(5);
    for (int i = 0; i < 5; i++) p[i] = i;
    p[find(p, 1)] = find(p, 2);
    cout << (find(p, 1) == find(p, 2)) << endl;
    cout << (find(p, 1) == find(p, 3)) << endl;
    return 0;
}

換你了

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

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

這一課你做了什麼

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

如果卡住了