並查集 (Disjoint-set Forest)

並查集是一個將彼此有關係的人們迅速分類成各自的小團體的一種常見技巧，主要透過兩種集合的操作 find (查找某人屬於哪個團體) 和 union (合併兩個團體) 來進行。背後的原理如下：每個團體都是一張位階分明的有向無環圖 (directed-acylic graph)，每個人都會指向自己的 (直屬) 長官，而唯一一位自己就是自己長官的人 (士官長曰：你各位要自律啊！) 我們就稱之為團長 (leader)。由此定義，如果兩個人各自持續向上追查自己的長官、自己的長官的長官、自己的長官的長官的長官，依此類推，最後會追查到同一位 leader，我們就能推測這兩個人是屬於同一個團體，反之就是不同，這個動作我們稱之為 find。至於 union，標準作法則是把其中一位團長的長官 (原本是自己) 指定為另一位團長，有點類似投降的意味，這樣的話原本分屬兩個團體的團員持續向上追查自己長官的最終結果就勢必為同一位團長，於是這兩個團體就合併了！

如何實作？我們會透過一個陣列 p[i] 來記錄第 i 位的長官。一開始每個人都分屬不同的團體，因此自己就是自己的長官。這段初始化是程式一開始一定要做的。

const int N = 10; int p[N]; // p 是 parent 的意思
for (int i=0; i<N; i++)
    p[i] = i;

計算過程中每次在追查完自己所屬團體的團長之後，也能順便讓團長直接變成自己的直屬長官 (path compression)，如此一來能加速追查結果，而且不影響正確性。

int find(int x) {
    return x == p[x] ? x : p[x] = find(p[x]); // 中間的 "p[x] =" 又被稱為 path compression 技巧
}

合併兩個人的所屬團體的實作如下。

void _union(int x, int y) { // 因為 C++ 已內建 union 關鍵字，為了避免衝突只好加上前綴底線
    x = find(x); y = find(y);
    p[x] = y; // 或者 p[y] = x; 也可以，看個人喜好。
}

另外值得一提的是，在某些題目裡面每個團體可能會附帶一些解題所需要的額外資訊，此時在做 union 的時候如果硬是要把資訊量多的團體併向資訊量少的那邊，那麼在更新額外資訊的時候不但費時而且沒有任何額外的好處，為了避免這樣的狀況發生導致 TLE，實務上會先行比較兩邊團體所帶的資訊量，這樣我們就能確保是資訊量少的團體併向資訊量多的那邊。

只是我們要注意到上一段提到的問題和一般演算法課本所提到的問題並不相同，演算法課本主要是針對 forest 本身的結構做優化，它並不考慮解題所需要的額外資訊，而實務上板主只需要利用一般常見且容易實作的 path compression 技巧就能 AC，所以一般來說如果不帶額外資訊的話通常不需要花腦筋去想到底是要從 A 合併到 B 還是從 B 合併到 A。