併查集

🎯 什麼情境該想到我

當你「要一直合併群組，並隨時問『這兩個在同一組嗎』」的時候——連通性、帳號去重合併、朋友圈、網路連通、Kruskal 最小生成樹。
★ 它是**少數「兩行優化把複雜度從 $O(\log n)$ 壓到幾乎 $O(1)$」**的資料結構。

⚙️ 怎麼用（機制與兩個優化）

結構：森林

每個集合是一棵樹，用「樹根」代表整個集合。

初始：  0  1  2  3  4          每個點自成一組

union(0,1), union(2,3)：
        0     2    4
        |     |
        1     3

union(1,3)：
          0        4
        /   \
       1     2
             |
             3
       find(3) = 0，find(1) = 0  → 同一組

基本實作（兩個優化缺一不可）

type DSU struct {
    parent []int
    rank   []int      // 樹高的上界（也可用 size）
    count  int        // ★ 目前的集合數量 —— 免費且常用
}
 
func NewDSU(n int) *DSU {
    p := make([]int, n)
    for i := range p { p[i] = i }
    return &DSU{parent: p, rank: make([]int, n), count: n}
}
 
// ★ 優化一：路徑壓縮
func (d *DSU) Find(x int) int {
    if d.parent[x] != x {
        d.parent[x] = d.Find(d.parent[x])   // 回程時把沿路所有節點直接掛到根上
    }
    return d.parent[x]
}
 
// ★ 優化二：按秩合併
func (d *DSU) Union(x, y int) bool {
    rx, ry := d.Find(x), d.Find(y)
    if rx == ry { return false }            // 已在同一組（Kruskal 用這個判斷成環）
    if d.rank[rx] < d.rank[ry] { rx, ry = ry, rx }
    d.parent[ry] = rx                       // ★ 矮的掛到高的下面
    if d.rank[rx] == d.rank[ry] { d.rank[rx]++ }
    d.count--
    return true
}

★ 兩個優化各自在做什麼

優化	做什麼	單獨使用的複雜度
按秩合併	矮樹掛到高樹下，避免樹長成一條鏈	$O(\log n)$
路徑壓縮	Find 時把沿路的節點全部直接接到根上	攤還 $O(\log n)$
★ 兩者一起	—	攤還 $O(\alpha (n))$

為什麼「按秩合併」有效：如果總是把高樹掛到矮樹下，樹會越長越深。
反過來掛，可證明秩為 $r$ 的樹至少有 $2^r$ 個節點 → 樹高 $\le {\log }_{2}n$。

為什麼「路徑壓縮」有效：每次 Find 都在攤平這棵樹。做過一次之後，
沿路所有節點的下一次 Find 都是 $O(1)$。

★ $\alpha (n)$ 是什麼（這是最值得記住的一點）

$\alpha$ 是 Ackermann 函數的反函數，成長速度慢到荒謬：

$\alpha (n)\le 4\text{對所有 }n\le 2^{2^{2^{65536}}}$

★ 也就是說：對任何「宇宙中可能存在的資料量」，$\alpha (n)<5$。
實務上就當成常數。 併查集是實質 $O(1)$ 的。

（Tarjan 證明了 $\Theta (m\alpha (n))$ 是緊界——不可能再更好。）

主要應用

應用	做法
★ Kruskal 最小生成樹	Union 回傳 false 就代表會成環，跳過這條邊
連通分量計數	維護 count，每次成功 union 就減一
動態連通性	「加邊之後 a 和 b 連通了嗎」—— ★ 比重跑 深度優先搜尋 快得多
★ 帳號／實體合併	「這兩筆記錄是同一個人」→ union。實務上極常用（CRM 去重、ID 映射、爬蟲的實體解析）
等價關係	任何「a 等價於 b」的傳遞閉包
★ 帶權併查集	在 parent 邊上存「相對關係」（差值、比例），可以回答「a 比 b 大多少」——用於食物鏈、匯率、方程組一致性檢查

★ 它做不到什麼（重要的邊界）

做不到	為什麼
★ 刪除／拆分（un-union）	路徑壓縮破壞了歷史結構，無法還原。 → 需要拆分就得用 link-cut tree 或離線處理（把刪除反轉成加入，倒著跑）
列出某個集合的所有成員	只知道根，不知道成員。要另外維護一個 map[root][]member
有向圖的連通性	併查集處理的是無向等價關係。有向圖的強連通分量要用 Tarjan（見 深度優先搜尋）

★ 「不能拆分」是最常被忽略的限制。 需求裡只要出現「取消合併」，併查集就不是答案。

🧪 我實際套用的紀錄

• （待填）

⚠️ 注意 / 什麼時候不適用

• ★ 一定要兩個優化都做。只做一個是 $O(\log n)$，兩個一起才是 $\alpha (n)$。少寫一個不會出錯，只會慢——很難察覺。
• Find 的遞迴在極端情況會很深（雖然路徑壓縮後很快變淺）。保守可以寫迭代版（兩趟：先找根、再壓縮）。
• 不能拆分（見上）。
• 按秩合併用 rank 或 size 都可以，但壓縮之後 rank 只是「高度的上界」不是真實高度——不要拿它當樹高用。
• 並行環境需要額外設計（無鎖併查集存在但複雜）。
• 只要靜態連通性就用 深度優先搜尋：一次 $O(V+E)$ 標記完所有分量，更簡單。併查集的價值在「動態加邊」。

🔗 相關工具

• Kruskal 最小生成樹 —— 最主要的客戶
• 深度優先搜尋 —— 靜態連通性的替代方案
• 拓撲排序 —— 有向相依關係（不同問題，別混淆）
• 雜湊表 —— 非整數的元素要先映射成索引
• 演算法導論