理論

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

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

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

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

StackOverflow 文件

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

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

StackOverflow 文件

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

StackOverflow 文件

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

StackOverflow 文件

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