用於克魯斯卡演算法的並查集（union-find）

克魯斯卡演算法把同一個問題問上千次：「這兩個城鎮已經在我網路的同一個連通塊裡了嗎？」若是，它們之間的電纜會造出浪費的迴圈，應該跳過。你需要一個方法來回答這個問題，並在確實加入電纜時合併兩塊，兩者都要快得驚人。並查集正是為此、且僅為此打造的微小資料結構。

並查集維護一組互斥集合，支援兩個操作：find(x) 回傳一個代表元素以辨識 x 所屬的集合，union(x, y) 合併含 x 與含 y 的兩個集合。它以森林儲存：每個元素指向一個父節點，而每棵樹的根是該集合的代表。兩頂點同屬一集，恰當 find 把它們往上走到同一個根時。兩個優化使它快得驚人。按秩合併把較矮的樹接在較高的樹下，使樹保持淺。路徑壓縮使一次 find 中走過的每個節點之後直接指向根，把樹壓平以利下次。兩者合起來給出每次操作的攤還成本 O(alpha(n))，其中 alpha 是反阿克曼函數——對任何可能出現的 n 而言實際上是個小常數（小於 5）。

在克魯斯卡中，每條邊對其兩端點各觸發一次 find（同根即同分量，故拒絕該邊），而當邊被接受時，觸發一次 union 來合併分量。因為每個操作都攤還近乎常數，整個連通性記帳約花 O(E alpha(V))，被 O(E log E) 的邊排序遠遠蓋過——所以相對於排序，並查集幾乎是免費的。兩個誠實的提醒：alpha(n) 是攤還的，意指一串操作的平均極小，儘管單次 find 仍可能走較長的路徑；而基本的並查集支援合併與查詢，但不支援把集合再拆開，這就是它完美契合克魯斯卡只加不刪的流程，卻不適合會刪邊的問題的原因。