併查集通常被簡稱為 DSU（Disjoint Set Union），就如它的英文名字所說，是一種維護集合的資料結構。它的目標是這樣的：有 $n$ 個元素 $1,2,\dots,n$，一開始每個元素自己身處於只有它的集合，然後這個資料結構支援以下操作：

• 合併（Union）：對於兩個元素 $x,y$，把它們所在的集合合併成同一個集合。
• 尋找（Find）：對於某個元素 $x$，查詢它在哪一個集合。通常這個操作是為了判斷兩個元素是不是在同一個集合裡，所以一般來說，這個詢問的答案是一個代表那個集合的數字，如果代表兩個元素身處集合的數字一樣，這兩個元素就在同一個集合裡。

我們用個比較平易近人的方式來說，現在課堂上有 $n$ 個人要分組，一開始每個人自己是一組，然後會發生一些事件，事件有兩種：

• 老師指定了兩個人，這兩個人所屬的組別要合併成同一組。
• 老師想知道某兩個人是不是在同一組裡。

你的目標就是回答老師的問題。

我們先想想要怎麼知道兩個人是不是在同一組。要是我們的作法是直接去跟其中一個人問「欸某某跟你同一組嗎？」那每個人就都得知道自己組裡的所有成員有誰，但不見得每個人記憶力都這麼好，而且組內的人還會越來越多，要求每個人都要在組別合併之後馬上認識所有的新組員不太可能。

一個現實生活中比較有可能的方法是讓每一組都有一個組別編號，只要分別問那兩個人自己的組別編號是什麼，看看是否一樣就知道他們是不是在同一組了，這在現實世界很容易做到，只要在兩個組 $x,y$ 合併的時候，大聲宣布「組別 $x$ 併入組別 $y$ 了，第 $x$ 組的人以後就是第 $y$ 組的人」，這樣本來在第 $x$ 組裡的人以後就會說自己的組別編號是第 $y$ 組。要寫成程式就不太容易了，要是我們開一個陣列記錄每個人所在的組別編號，要合併時把第 $x$ 組裡所有人的組別編號改成 $y$，這樣每次都要花上 $O(\text{組別 } x \text{ 的大小})$ 的時間，如果我們的過程是這樣的話……

• 第 $1$ 組併入第 $2$ 組，本來第 $1$ 組的大小是 $1$。
• 第 $2$ 組併入第 $3$ 組，本來第 $2$ 組的大小是 $2$。
• 第 $3$ 組併入第 $4$ 組，本來第 $3$ 組的大小是 $3$。
• ……
• 第 $i$ 組併入第 $i+1$ 組，本來第 $i$ 組的大小是 $i$。
• ……
• 第 $n-1$ 組併入第 $n$ 組，本來第 $n-1$ 組的大小是 $n-1$。

這樣全部要花上 $1+2+\dots+(n-1)=O(n^2)$ 的時間，有一點太久了。重點在於我們不可以要求「組別合併時每一個人都要立刻更新自己所在組別的資訊」。

既然用組別編號行不通，那不如我們混合一下以上兩種方法。要是每一組都有一個「組長」，所有組員都一定知道他是誰，這樣想知道兩個人是不是同一組的時候，就只要去問他們「你們的組長是誰」，看看是不是同一個人就好。但剛才說了，我們不可以要求組別合併時，每一個組長有變的人都要馬上知道自己的組長改變了，其實我們不需要這麼要求，我們只需要在問某一個人他的組長是誰的時候，請他先去問問他認為的組長「你現在還是組長嗎，不是的話那組長是誰」就好了，要是發現那個舊組長回答的組長現在也不是組長了，就繼續往上問。

講得清楚一點，可以當作每一個人都有自己認為的組長，先叫作「直屬上司」好了，組長的直屬上司是自己。要知道一個人的真正組長是誰，就先看看他的直屬上司是不是組長、不是組長就再查他的直屬上司，一直查到找到組長是誰為止，這樣我們只要確保

• 每一個不是組長的人，心裡都有一個直屬上司。
• 組長知道自己是組長，也就是組長心裡的直屬上司就是自己。
• 不是組長的人，他的直屬上司的直屬上司的直屬上司……不管幾層都一定不是自己，不然問一問就會問回同一個人，永遠找不到組長是誰。

發現了嗎？這可以看作是一個樹狀結構，每一個組別都是一棵樹，根節點是組長，每個節點的父節點就是直屬上司。當詢問兩個人是不是在同一組時，我們想知道的是他們所在的樹根節點是不是一樣，而當要合併兩組時，我們只要把其中一棵樹的根節點接到另一棵樹的根節點下面、也就是改變其中一組組長的直屬上司，變成另一組的組長就好了。

struct DSU_bad {
    // dsu[i] = i 心裡的直屬上司，我們使用 1-based
    vector<int> dsu;
    DSU_bad(int n): dsu(n + 1) {
        iota(dsu.begin(), dsu.end(), 0);
    }
    // 找 a 的組長是誰
    int findDSU(int a) {
        // 自己不是組長，看直屬上司的組長是誰
        if (a != dsu[a]) return findDSU(dsu[a]);
        // 自己是組長
        return a;
    }
    // 把 a,b 所在的組別合併
    void unionDSU(int a, int b) {
        a = findDSU(a);
        b = findDSU(b);
        dsu[b] = a;
    }
};

不過，很遺憾的是這樣子的時間複雜度還是很大，每次詢問一個人的組長是誰，都要一步一步走到他所在的樹的根節點，要是他的深度很大，那詢問時間就會很久。舉例來說，剛才舉的會花到 $O(n^2)$ 時間的例子裡，在這個作法下就會變成

• 把 $1$ 的父節點改成 $2$，現在 $1$ 的深度是 $1$。
• 把 $2$ 的父節點改成 $3$，現在 $1$ 的深度是 $2$。
• 把 $3$ 的父節點改成 $4$，現在 $1$ 的深度是 $3$。
• ……
• 把 $i$ 的父節點改成 $i+1$，現在 $1$ 的深度是 $i$。
• ……
• 把 $n-1$ 的父節點改成 $n$，現在 $1$ 的深度是 $n-1$。

整個樹由下到上會是依序為 $1,2,\dots,n$ 的鏈，如果老師想問是否在同一組的人都處在這棵樹的深處，每次都會要問很久。

要做到比較好的時間複雜度，我們有一些看似是小聰明的方法可以使用。

剛才會有時間複雜度噴飛的問題，是因為有些人深度很大，每次問他們的組長是誰都要很久，但其實不用每次問一個人都全部重問一遍，當我們去問一個人「你的組長是誰」並且輾轉得知他的真正組長之後，他就可以把心中想的直屬上司改成他的真正組長了，剛才問的那一連串的直屬上司也都可以這麼做，下次問他們的時候就不必重問一遍。

struct DSU_path_compress {
    vector<int> dsu;
    DSU_path_compress(int n): dsu(n + 1) {
        iota(dsu.begin(), dsu.end(), 0);
    }
    int findDSU(int a) {
        // 去問問本來的直屬上司新的組長是誰，也順便把直屬上司直接改成組長
        if (a != dsu[a]) dsu[a] = findDSU(dsu[a]);
        // 現在直屬上司就是組長了
        return dsu[a];
    }
    void unionDSU(int a, int b) {
        a = findDSU(a);
        b = findDSU(b);
        dsu[b] = a;
    }
};

聽起來是奇怪的常數優化，令人吃驚的是，這個方法中，如果有 $m$ 次詢問（包含 unionDSU() 裡面呼叫的 findDSU()，不含遞迴的呼叫）的話，那總時間複雜度會是
\[ \Theta(n + m \cdot (1 + \log_{2 + m/n} n)) \]
因為這個複雜度太怪了，所以我們就不說明背後的原理，有興趣的讀者可以自己搜尋，並且通常我們就只說它是 $O(n + m \log n)$，一個操作的均攤時間複雜度是 $O(\log n)$。（因為 unionDSU() 總是需要呼叫 findDSU()、額外時間是 $O(1)$，所以在這裡它們的時間複雜度是一樣的。）

這個方法用樹的語言來解釋，就是在詢問一個節點的根是誰時，把根到它的路徑之間上面的所有節點，都變成根的子節點，就像把這條路徑壓縮了一樣，所以這個方法叫作路徑壓縮。

先把路徑壓縮丟一邊，這是另一個不同的作法。剛才在合併組別時，我們一直都是隨便挑其中一組的組長，成為合併後的組長，程式碼裡面呼叫 unionDSU(a, b) 都是讓 a 的組長當新組長，所以老師就也可以很壞的讓我們最後的樹變成一條鏈。要是我們改變策略，用某種比較有道理的方式選擇組長呢？像是本來領導比較多人的組長，感覺就比較有能力，所以我們讓比較大的那一組的組長當新的組長。

為此，我們需要知道每個組別的大小，才能在合併時決定新組長是誰。這件事情很簡單，只要讓每個組長都隨時掌握自己組內有多少人就好了。

struct DSU_heuristic {
    vector<int> dsu, sz; // sz[i] = i 當組長的組有多大
    DSU_heuristic(int n): dsu(n + 1), sz(n + 1, 1) {
        iota(dsu.begin(), dsu.end(), 0);
    }
    int findDSU(int a) {
        if (a != dsu[a]) dsu[a] = findDSU(dsu[a]);
        return dsu[a];
    }
    void unionDSU(int a, int b) {
        a = findDSU(a);
        b = findDSU(b);
        if (a == b) return;
        // 讓 a 是比較大的那一組
        if (sz[a] < sz[b]) swap(a, b);
        dsu[b] = a;
        sz[a] += sz[b];
    }
};

這個方法裡，一個操作的 worst-case 時間複雜度是 $O(\log n)$，原因很簡單，每次有人的組長改變時，代表他的組被併入一個更大的組了，所以他所在的組大小變成本來的兩倍，而他在樹上的深度（注意現在沒有路徑壓縮）就是他改變組長的次數，因此每個人的深度最多是 $\log_2 n = O(\log n)$。這個方法叫作啟發式合併，這是一個不只會用在 DSU 的技巧，讀者可以先把這個名稱記在心裡，以後的章節還會再出現這個。

啟發式合併還有另一種寫法是記錄每一組裡面的最大深度，合併時把最大深度比較小的併進比較大的那一組。用大小合併的方法叫作 union-by-size、用深度合併的方法叫作 union-by-rank，沒有什麼太大差別，只是有些複雜度分析在 union-by-size 比較簡單、有些在 union-by-rank 比較簡單。

如果我們把路徑壓縮和啟發式合併一起使用，那 $m$ 個操作的總時間複雜度就會神奇的變成 $O((n+m) \alpha(n))$，$\alpha(n)$ 是反阿克曼函數，簡單來說它就是一個成長得非常非常慢的函數，對於在正常的競賽題目裡面會出現的 $n$，與之對應的 $\alpha(n)$ 都不會超過 $4$，簡直就和常數差不多，但基於演算法的道德，寫時間複雜度的時候還是要把它寫出來。

struct DSU_combined {
    vector<int> dsu, sz;
    DSU_combined(int n): dsu(n + 1), sz(n + 1, 1) {
        iota(dsu.begin(), dsu.end(), 0);
    }
    int findDSU(int a) {
        if (a != dsu[a]) return findDSU(dsu[a]);
        return a;
    }
    void unionDSU(int a, int b) {
        a = findDSU(a);
        b = findDSU(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        dsu[b] = a;
        sz[a] += sz[b];
    }
};

有很多人在沒有特殊需求的時候，會只寫路徑壓縮，畢竟路徑壓縮比較好寫又已經跑得很快了，只要在時間複雜度很危險，可能會 TLE 的時候再加上啟發式合併就好，不過也會有些特殊的場合不能用路徑壓縮，就必須得用啟發式合併。在沒什麼特殊需求的時候，可以選擇自己喜歡的優化方式，讓複雜度是 $O(\log n)$，需要讓程式跑得更快或是行有餘力再兩個都用上就行了。

我們把節點想成人、連通塊想成組別，這樣加邊就是合併兩個組別。不過這題想知道的詢問並不是「兩個節點是不是在同個連通塊裡面」，而是要問連通塊數量和最大連通塊。最大連通塊我們其實已經會了，只要像在啟發式合併時做的那樣，讓組長隨時都知道自己組內有幾個人，合併之後更新一下答案就好，而算連通塊數量其實也很簡單，每次有兩組合併，數量就會少 $1$、一開始數量是 $n$，用 DSU 就能輕鬆解決。

#include <bits/stdc++.h>

using namespace std;

struct DSU {
    vector<int> dsu, sz;
    int max_sz = 1, cnt;
    DSU(int n): dsu(n + 1), sz(n + 1, 1), cnt(n) {
        iota(dsu.begin(), dsu.end(), 0);
    }
    int findDSU(int a) {
        if (a != dsu[a]) return findDSU(dsu[a]);
        return a;
    }
    void unionDSU(int a, int b) {
        a = findDSU(a);
        b = findDSU(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        dsu[b] = a;
        sz[a] += sz[b];
        max_sz = max(max_sz, sz[a]);
        cnt--;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        dsu.unionDSU(u, v);
        cout << dsu.cnt << " " << dsu.max_sz << "\n";
    }
}

蛤，這題看起來跟 DSU 一點關係也沒有。我們先討論一下，當我們在加水的時候，這次加入的水究竟會跑進哪一個容器裡面。假設我們現在要在容器 $p$ 加 $x$ 單位的水，那麼這些水會最先流入編號 $\geq p$ 的第一個還沒有滿的容器裡面，如果還有多餘的水，就會再往下一個還沒有滿的容器流，直到水加完了或是流到地上為止。因此，我們會想要做的事情是快速地找到編號 $\geq p$ 的第一個還沒有滿的容器。

    // cap[p]: p 的容量
    // water[p]: p 裡的水
    // get_next(p): 編號 >= p 第一個還沒滿的容器，沒有的話回傳 n+1
    auto add_water = [&](int p, int x) {
        while (x > 0 && p <= n) {
            p = get_next(p);
            int t = min(x, cap[p] - water[p]);
            water[p] += t;
            x -= t;
        }
    };

因為每次執行到 while 裡的內容時，都會發生以下狀況的至少一種：

• 把一個本來還沒滿的容器填滿（在 cap[p] - cap[water] <= x 的時候），這件事情只會發生在每種容器上一次，所以總共只會發生 $n$ 次。
• 把我們要加的水全部加完（在 x <= cap[p] - cap[water] 的時候），每次加水只會發生一次。

所以這個 while 迴圈總共只會執行 $n+m$ 次而已，如果我們可以實作出一個很快的 get_next，就能用不錯的時間複雜度通過這題。

但是要怎麼有效率的找到第一個還沒滿的容器呢？我們直接按照本來題目的路線想，如果 $p$ 已經滿了，那等同於我們試著把水加進 $p+1$ 裡面，如果 $p+1$ 已經滿了，等同於我們試著把水加進 $p+2$ 裡面、……，直到我們試著把水加進一個還沒滿的容器為止，所以可以想成

• 如果 $p$ 已經滿了，那它就是跟 $p+1$ 同一組的，因為往它們裡面加水最後都會跑到同一個地方。

所以我們先開一個 DSU，然後在這個 while 迴圈的最後加上 if (cap[p] == water[p]) dsu.unionDSU(p, p + 1);，我們可以把 DSU 開成有 $n+1$ 個元素，來方便我們處理流到地上的狀況，也就是假裝地板是第 $n+1$ 個容器，但我們不會往裡面加水、它也不會滿。這樣一來，每一組裡面的最後一個容器，就是我們對這組裡任何一個容器呼叫 get_next 時的答案。

剩下來的事情，就是要知道一組裡面最後一個容器是誰了。一種方式就像上面記錄每一組的大小一樣，讓每一組的組長去記錄「這一組裡最後一個容器是誰」，這樣就可以獲得一個 $O(\alpha(n))$ 時間的 get_next 了。

struct DSU {
    vector<int> dsu, sz, last;
    DSU(int n): dsu(n + 1), sz(n + 1, 1), last(n + 1) {
        iota(dsu.begin(), dsu.end(), 0);
        iota(last.begin(), last.end(), 0);
    }
    int findDSU(int a) {
        if (a != dsu[a]) return findDSU(dsu[a]);
        return a;
    }
    void unionDSU(int a, int b) {
        a = findDSU(a);
        b = findDSU(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        last[a] = max(last[a], last[b]); // 多了這個
        dsu[b] = a;
        sz[a] += sz[b];
    }
};

    DSU dsu(n + 1);
    auto get_next = [&](int p) {
        return dsu.last[dsu.findDSU(p)]; // 要問組長，記得要寫 dsu.findDSU(p)
    };

另一種方法是，如果你不想用啟發式合併，只用路徑壓縮的話，其實你是可以指定合併兩組時誰要是組長的，只要讓最後一個容器永遠是組長，就不需要像這樣子多開一個 last 陣列來儲存每一組的最後一個容器是誰，組長他自己就是了。

併查集是一個實作簡單卻有不少用處的資料結構，除了題目明目張膽地是一個跟分組有關的問題時可以使用外，像 Vessels 這種「要跳過一段東西」的問題也可能可以派上用場，甚至還可以維護一些跟組別相關的資訊，將來讀者還會不斷地遇見它。