並查集又稱不相交集資料結構，其實是之前討論過的資料樹的延伸。剛開始的樹每一個都是獨立的，一棵樹只有一個節點。在透過尋找相同的根節點 (root)，來將這些樹逐漸合併的過程，最終成為一棵完整的樹。就讓我們用下面的例子來一一解釋整個過程。

問題是這樣的。在班上每個人都是獨立的，但總會有很多的小團體。今天你是老師，為了要認識學生，就要先找到每個小團體中的主要人物。可是你不知道他們是誰，你只得到零碎的一些訊息，比如誰跟誰比較好等等。而我們必須要把這些訊息一一合併歸類，最終找到誰屬於哪個團體，誰是其中的主要人物。

首先我們知道班上有 10 個學生，而你有 9 條線索，每個線索都是倆倆相對的。

students = 10
leads = 9
clues = [[1, 2], [3, 4], [5, 2], [4, 6], [2, 6], [8, 7], [9, 7], [1, 6], [2, 4]]

我們先設一個一維陣列，裡面有全部的學生的號碼。

所以這時候的狀態變成：

總結幾項特點：

• 在合併線索的時候，遵守「靠左原則」。
• 當先所有重複的時候，遵守「擒賊先擒王」。
• 在判斷兩個學生是否在同一個小團體的時候，要注意必定要找到其根源，中間穿插的小團體不算什麼，必須要找到最根本的。

全部的程式碼

# people = 人數; leads = 線索數
people, leads = map(int, input().split(' '))

# 初始化每個人的編號
f = []
for i in range(people):
    f.append(i)

# 「擒賊先擒王原則」，不斷的找，找到小團體裡面的頭為止。
def getf(f, v):
    if f[v] == v:
        return v
    else:
        # 路徑壓縮 (path compression)，每次在函數返回的時候，
        # 順道把路上遇到的「頭頭」改為最後找到的「大頭編號」，也就是小團體的主要人物。
        # 這樣可以提高以後找主要人物的速度。
        f[v] = getf(f, f[v])
        return f[v]

# 合併兩個小團體的函數
def merge(f, v, u):
    t1 = getf(f, v)
    t2 = getf(f, u)
    if t1 != t2 : # 判斷兩位學生是否同屬一個小團體，及是否同一個頭頭。
        f[t2] = t1
        # 「靠左原則」，左邊變成右邊的頭頭。即把右邊的集合，變成左邊的子集合。
        # 經過路徑壓縮以後，將f[u]的根的值也指定為v的大頭f[t1]

'''
測試資料 (test data) :
10 9
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4
'''

# 開始合併線索
for i in range(leads):
    clue1, clue2 = map(int, input().split(' '))
    merge(f, clue1, clue2)

# 掃描最後有幾個獨立的小團體
sum = 0
for j in range(people):
    if f[j] == j :
        sum += 1

print(sum)

'''
answer = 3
'''