接下來的幾個章節，會從幾個特定的問題開始，藉由使用不同的資料結構，展示出對程式效能的影響。首先介紹一個經典的動態連結的問題（Dynamic connectivity），例如把判斷臉書任意兩個用戶是否有共同好友，假設沒有共同好友，如果有一天這兩個用戶個別的好友中，有人互相成為好友，則原來的兩個用戶即擁有共同好友。
舉例來說 Evan 和 Joe 原本沒有共同好友，可是在各自的好友 Willy 和 Jack ，一旦這兩個人成為好友，Evan 和 Joe 則會擁有共同的好友。
互斥集（Disjoint sets）、併查集（Union-find sets）都只是形容同一個抽象的資料結構，用來處理類似的問題，其中可以使用兩個方法
- isConnected(x, y) 判斷兩個用戶是否有共同好友
- connect(x, y) 將兩位沒有共同好友的用戶，互相成為好友
為了方便介紹，先將集合內的元素都先當成是正整數，因此，這裡可以定義一個併查集介面，規定任何實現這個介面的類別，都要實作上述兩個方法
public interface DisjointSets {
void connect(int p, int q);
boolean isConnected(int p, int q);
}
直覺第一個實作這個介面的方法會將每一對 connected 的元素關係以某種形式記錄下來，不過更好的方法是利用之前學過的資料結構：集（Set），將有關聯的元素會在同一個集內。
ListOfSets
不過接下來第二個問題是要使用哪一種資料結構存放 N 個集？根據之前所學，直覺上可以選擇用一個列表（List）List<Set<int>>，來存放這些正整數集，接著開始思考如何實作介面的方法
[{1}, {2, 3}, {4, 5, 6}]- connect(x, y)
遍歷列表所有的集，找到 x 以後，將 y 加入 x 所在的集內。 - isConnected(x, y)
遍歷列表所有的集，找到 x 以後，判斷 y 是不是在 x 所在的集內。
到目前為止這似乎是一個不錯的方法，以一個可行的資料結構實作併查集介面，接下來只剩下撰寫代碼的工作而已。然而，實際上實作併查集的資料結構並不會使用列表，介紹下一個資料結構以後，則會發現比較下來使用列表並不是一個好的方法。
Quick Find
除了用列表以外，可以改成使用存放整數的陣列（array），陣列的每個指標（ index） 代表每個 N-1 個正整數，而陣列存放的整數代表該正整數的所屬 "ID"，擁有相同 ID 的正整數代表有關聯，舉例來說正整數 0 、1、3、5 有關聯時，陣列則如圖所示。
同樣地接下來思考如何實踐介面的兩個方法
- connect(x, y)
遍歷陣列所有 index，將 x 所屬的 ID 改為 y 所屬的 ID。 - isConnected(x, y)
判斷兩個 index 的 ID 是否相同。
和 ListOfSets 相比其中最大的差異為實踐 isConnected 的方法，不再是遍歷所有的元素，而是只要檢查陣列中兩個 index 的 ID 是否相同即可，因為透過 index 存取陣列的速度相當快，顯著降低了執行所花費的時間。
從這兩個例子可以發現一開始選擇的資料結構，存放集的列表或是存放整數的陣列，對於想要實作的介面具有根本的影響力以及重要性，包括代碼撰寫的複雜度以及執行所花費的時間，因此如何選擇基礎的資料結構以完成介面或更高階的資料結構（e.g. DisJoint sets），變成往後重要的課題。
Quick Union
接下來要繼續改進的是方法 connect，不管是 Quick Find 或是 ListOfSets，都會發現需要遍歷所有資料結構內的資料，此時思考如何像 Quick Find 中改進 isConnected 的方式，只改變一個 index 所屬的 ID，即可將兩個 set 合併成一個 set。
其中一個想法為稍稍改變每個 index 所屬 ID 的規則，不再是統一同一個 Set 的 ID，而是將屬於同一個 set 內的資料，用一種"樹狀"關係表示，每一個正整數都屬於另一個正整數，其中不屬於任何正整數的元素則視為最上層的根元素。
舉例來說，四個正整數 0, 1, 2, 3 互相關聯屬於同一個 set，其中一個正整數 0 的身分為最上層的根元素（root），在陣列內的值為任一負數，代表其它整數皆依附在根底下。正整數 1 和 0 同屬一個 set，則陣列中 index = 1 的值為正整數 0，代表 1 依附在 0 底下；正整數 3和 0, 1 同屬一個 set，則陣列中 index = 3的值為正整數 1，代表 3 依附在 1 底下，以此類推如圖所示。這 6 個正整數共形成 3 個 set，分別的根元素為 0、4、 5。
此時如果想要關聯兩個 set，則不再需要一一將陣列內同一個集的每個 index 賦予相同的值，而是將其中一個 set 的根，賦予另一個 set 的根的值，換句話說就是關聯兩個 set 的根，即可實現方法 connect。
舉例來說，connect(2, 4) 只需要將 4 所屬 set 的根元素，在這裡即 4 本身，的值改為 2，即可關聯兩個 set。亦或是改為 2 所屬的根元素 0，也可以達到相同的效果。
然而，考慮下圖的特殊的情況，會讓這棵樹的高度會和整數的數量成正比的關係，導致在搜尋根（e.g. find(4)）的時候，還是需要遍歷陣列內所有的元素，損失搜尋的效能，因此接下來的問題是如何改善兩棵樹在連結的時候，降低樹的高度成長的速度。
Weighted Quick Union(WQU)
其中一個方法為，當在連結兩棵樹的時候，先比較各自的數量，此時有兩個選擇
- 將數量少的樹接到數量多的樹
- 將數量多的樹接到數量少的樹
可以從兩種結果發現選項 1 對於連結後的樹的高度的成長速度較緩慢，舉例來說，經過圖五的連結的順序，除了根元素以外，其餘元素皆會在根元素底下，如圖六所示。
經過數學證明，利用樹狀結構來儲存資料的話，isConnected 和 connect 這兩個方法的時間複雜度皆為 O(logN)，其中 N 為元素的數量。雖然不是 O(1)，不過相較於 O(N)，已經顯著的提升了執行的效率。
另外直觀上在選擇如何連結兩棵樹的時候，也可以將比較大小改為比較高度，不過代碼會變得比較複雜且複雜度並沒有改變，因此實際上還是會選擇比較樹的大小。
Weighted Quick Union with Path Compression
即便 WQU 已經能大幅提升 connect 和 isConnected 的效能，不過實際上可以再進行優化，在 WQU 不管是使用方法 connect 或是 isConnected，可以發現都會使用到搜尋根元素的方法 find。當在使用方法 find 的時候，除了找到根元素以外，同時將搜尋根元素的過程中所遍歷的元素，改變其隸屬關係，直接指向根元素。如此一來，當元素直接指向根元素時，搜尋根元素的的方法 find 將會變得非常迅速，整棵樹的結構也會變得相當扁平。
舉例來說，當搜尋 8 的根元素時，修改遍歷的所有元素 5、6、8 的所屬元素為根元素 1，接下來再一次執行 find(8) 時，就不必再經過元素 5、6，大幅提升搜尋的效率，如圖七所示。
