圖
並查集
並查集，又稱不相交集合資料結構，用來管理一批被劃分成若干組的元素，並能飛快地回答一個問題：這兩個元素在不在同一組？它支援兩種操作：find（這個元素屬於哪一組？）和 union（把含這兩個元素的兩組合併）。可以把它想成朋友圈——並查集能瞬間告訴你兩個人是否已經在同一個圈子裡，並把兩個圈子合併成一個。
每一組被存成一棵樹，每個元素指向一個父節點，樹根就是這一組的代表。find 沿著父指標一路走到根；union 把一個根掛到另一個根之下。如果樸素地做，這些樹會越長越高、越來越慢，所以要同時施加兩項最佳化。路徑壓縮在 find 過程中把途經的元素直接指向樹根，從而把樹壓扁。按秩（或按大小）合併總是把矮的樹掛到高的樹之下，讓樹保持低矮。
同時用上這兩項最佳化後，每次操作的攤還代價實際上是常數級——嚴格地說是 O(alpha(n))，其中 alpha 是反阿克曼函數，對你這輩子會遇到的任何輸入它都不超過約 4。這種近乎 O(1) 的速度使並查集成為 Kruskal 演算法內部的引擎——它能在常數時間內判斷加入一條邊是否會形成環——也使它成為連通性與分組類問題的常備工具。
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]); // path compression
return parent[x];
}
void unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return;
if (rank_[a] < rank_[b]) swap(a, b);
parent[b] = a;
if (rank_[a] == rank_[b]) ++rank_[a];
}find 把途經的每個節點直接指向根；union 把矮樹掛到高樹之下。
反阿克曼函數 alpha(n) 增長極慢，對任何實際的 n 都小於 5，所以人們常直接說並查集「每次操作實際上是 O(1)」。
又稱
另見