理論

聯合查詢資料結構提供以下操作：

• make_sets(n) 使用 n 單例初始化 union-find 資料結構
• find(i) 返回元素 i 的代表
• union(i,j) 合併包含 i 和 j 的集合

我們通過儲存代表我們 0 到 n - 1 元素的分割槽父的每一個元素 i 最終導致元素 parent[i] 代表含 i 集。
如果一個元素本身是一個代表，那麼它就是它自己的父元素，即 parent[i] == i。

因此，如果我們從單件集開始，每個元素都是它自己的代表：

我們可以通過簡單地遵循這些父指標來找到給定集合的代表。

現在讓我們看看如何合併集合：
如果我們想要合併元素 0 和 1 以及元素 2 和 3，我們可以通過將父級 0 設定為 1 並將父級設定為 2 來實現：

在這種簡單的情況下，只需更改元素父指標本身。
如果我們想要合併更大的集合，我們必須始終更改要合併到另一個集合的集合的代表的父指標 ：在合併(0,3)之後，我們設定了集合的代表的父節點包含 0 到包含 3 的集合的代表

為了使示例更有趣，我們現在也合併(4,5)，(5,6)和(3,4) ：

我要介紹的最後一個概念是路徑壓縮 ：
如果我們想要找到一個集合的代表，我們可能必須在到達代表之前遵循幾個父指標。我們可以通過將每個集的代表直接儲存在其父節點中來使這更容易。我們失去了合併元素的順序，但可能會有很大的執行時間增益。在我們的例子中，唯一未壓縮的路徑是從 0,4 和 5 到 3 的路徑：