iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 27
0
Software Development

30天學演算法和資料結構系列 第 27

[演算法] 並查集 (Union-find Algorithm)

  • 分享至 

  • xImage
  •  

並查集又稱不相交集資料結構,其實是之前討論過的資料樹的延伸。剛開始的樹每一個都是獨立的,一棵樹只有一個節點。在透過尋找相同的根節點 (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]]

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

id 1 2 3 4 5 6 7 8 9 10
f[id] 1 2 3 4 5 6 7 8 9 10
我們跟著線索慢慢的一步一步找。第一個線索是 1 號跟 2 號很要好。根據靠左原則,把左邊的當小團體的頭頭,
我們把 id = 2 的值改為 1,這樣就代表 1 號和 2 號同屬一個團體。
id 1 2 3 4 5 6 7 8 9 10
- - - - - - - - - - -
f[id] 1 1 3 4 5 6 7 8 9 10
接著是 3 號跟 4 號,同理,根據靠左原則,把 id = 4 的值改為 3 。
id 1 2 3 4 5 6 7 8 9 10
- - - - - - - - - - -
f[id] 1 1 3 3 5 6 7 8 9 10
再來是 5 號跟 2 號,這就表示 1 號跟 2 號、5 號都屬同字個團體的。這時問題就出現了, id = 2 的值本身已經為 1 了,但我們一樣根據靠左原則,把 id = 2 的值改為 5 。但在那之前,參照古人說擒賊先擒王的概念,我們要先把原本的頭頭 id = 1 的值先改為 5,就像f[f[2]] = f[5]這樣,之後再把 id = 2 的值改為 5。(為什麼要這樣,可以自己想一下。)

所以這時候的狀態變成:

id 1 2 3 4 5 6 7 8 9 10
f[id] 5 5 3 3 5 6 7 8 9 10
接著是 4 號跟 6 號:
id 1 2 3 4 5 6 7 8 9 10
- - - - - - - - - - -
f[id] 5 5 3 3 5 3 7 8 9 10
再來是 2 號跟 6 號,但 2 號本身的值(f[2])是 5,而 6 號的值則是 3 ,根據靠左原則,6 號要改成 2 號的值沒錯,但還有擒賊先擒王的概念在,我們要先改 3 號的值改成 5,才能接著將 6 號的值跟著改為 5。
id 1 2 3 4 5 6 7 8 9 10
- - - - - - - - - - -
f[id] 5 5 5 3 5 5 7 8 9 10
接著是 8 號跟 7 號:
id 1 2 3 4 5 6 7 8 9 10
- - - - - - - - - - -
f[id] 5 5 5 3 5 5 8 8 9 10
9 號跟 7 號:
id 1 2 3 4 5 6 7 8 9 10
- - - - - - - - - - -
f[id] 5 5 5 3 5 5 9 9 9 10
1 號跟 6 號,因為這兩個號碼都已經是屬於 5 的團體,這條線索就是冗餘的。
id 1 2 3 4 5 6 7 8 9 10
- - - - - - - - - - -
f[id] 5 5 5 3 5 5 9 9 9 10
2 號跟 4 號,但其實 f[2] = 5,f[4] = 3,而 f[3]又是屬於 5 的,最後發現其實 2, 3, 4 都是屬於同一個小團體,所以這條線索也是冗餘的。
id 1 2 3 4 5 6 7 8 9 10
- - - - - - - - - - -
f[id] 5 5 5 3 5 5 9 9 9 10
最後再找出有幾個集團就行了~

總結幾項特點:

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

全部的程式碼

# 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
'''

上一篇
[演算法] 最短路徑 (Floyd-Warshall 演算法)
下一篇
[演算法] 最短路徑 (Dijkstra 演算法)
系列文
30天學演算法和資料結構31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言