# Python-LeetCode 581 第13招 Union-and-Find and Minimum spanning tree
Union and Find(併查集)是一種資料結構，用來處理一群不相交的集合(disjoint set)，說是一種資料結構，應該是一套資料儲存方式與操作的演算法。併查集處理的資料是不相交的集合，如同它的名字，提供的主要操作有兩個：合併兩集合以及查詢某個元素在哪個集合中。
## 基本原理
為了方便說明，我們以人與社團來比喻元素與集合，一個人只能屬於一個社團。假設元素(人)的編號是0 ~ $n-1$，一開始每個人自己是一個社團。
我們先介紹直覺的天真做法，然後說明教科書上標準的做法。
### Union and Find 天真做法
既然要提供查詢與合併，直覺的做法就是用一個List紀錄每個人的所屬社團。像下面的寫法
```python=
# initial
for i in range(n): group[i] = i
# find the group of i
def ifind(i):
return group[i]
```
但合併時，必須將一個社團的成員全部改寫，我們必須知道每個社團的成員，所以，還需要一個list of list存每個社團的成員列表
```python=
# initial
for i in range(n): group[i] = i
member = [[i] for i in range(n)]
# find the group of i
def ifind(i):
return group[i]
# union group gi and gj
def union(gi,gj):
for i in member[gj]:
group[i] = gi
member[gi] += member[gj]
member[gj] = []
```
這樣的做法可以達到我們需要的兩種操作，效率好不好呢？我們可以看到，查詢永遠都是$O(1)$，但合併有可能很慘，這樣寫的話，合併的時間就是$member[gj]$的大小，如果將一個很大的社團併入一個很小的社團就會很花時間。
在最壞的狀況之下，我們可能每一回合將一個社團併入一個一人社團，下一回合又將這個合併後的社團併入另外一個一人社團，那麼，總共的合併時間就會是$1+2+3+\ldots +n-1=O(n^2)$。
不需要太聰明就可以找到一個改善的方法：**每次合併時，將比較小的社團併入大的社團**。
我們只要加一行，若$gi$比較小，就交換兩個社團。
```python=
# union group gi and gj
def union(gi,gj):
if len(member[gi]) < len(member[gj]):
gi,gj = gj,gi
for i in member[gj]:
group[i] = gi
member[gi] += member[gj]
member[gj] = []
```
這樣寫到底只是感覺比較好，還是有真的改善worst case time complexity呢？
事實上是將複雜度改善到$O(n \log n)$。我們想要去分析每次合併的時間不容易，但可以去分析每一個人被合併的總次數。因為我們都把小的併入大的社團，每個人所屬的社團每經過一次合併，社團成員就至少增加一倍，社團最後的大小不超過$n$，因此最多不會被合併超過$O(\log n)$次。全部$n$個人的合併總時間是$O(n \log n)$。
這個做法在大部分解題的場合應該都已經足夠通過。
### Union and Find 優化的標準做法
我們還是要介紹一下更好的做法。因為它並不難。
標準的併查集作法是一種樹狀圖的觀念，但是實作時完全以陣列來做就可以，也就是心中有樹但程式中無樹，寫起來非常容易，不容易寫錯，效率又高。
我們只要一個陣列就可以，依循樹狀圖的概念，陣列就叫做 $parent[]$。每一個人都會屬於某個社團，但不會屬於兩個社團。除了社長，每個人 $i$ 都有一個直接領導，就是他的衣食父母 $parent[i]$，社長就是社團的代表人，為了方便，若 $i$ 是社長，我們令$parent[i] = -x$，其中而 $x$ 是該社團中的總人數。我們可以用下列方式來操作合併與查詢：
```python=
def ifind(v):
while parent[v] >= 0:
v = parent[v]
return v
def union(u,v):
ru, rv = ifind(u), ifinc(v)
if ru == rv: return
# ru is the new root
parent[ru] += parent[rv] # total size
parent[rv] = ru
return
```
這個演算法很簡單，查找(ifind)時就一路沿 $parent[]$ 往上走，直到走到社長(代表元素)為止。合併的時候，先檢查兩者是否是同一社團，如果是就不需要做任何事，如果不是，就把其中一個社團社長的衣食父母改為另外一個社長，這就為成了合併的動作。與前面天真做法比較，這個做法不需要存 $member[]$。
這個方法雖然簡單，但是有個缺點，在一連串合併之後，可能有些人離社長關係非常遠，想像每次把一個社團都併入一個一人社團，這就如同社團每次都來一個空降的新人當新的社長，每併一次，最底下的那個人離社長的層級就增加一，這樣在查找的時候可能會很浪費時間。
改進的方法是這樣：每次合併時，把人數少的社團併入人數多的社團，也就是人多的社團社長當合併後的新社長。事實上，如果依照這個規定，社團的層級就不會超過 $\log(n)$。
證明：如果合併造成你離社長的層級增加1的話，表示你併入一個比原來更大的社團，也就是你的社團人數至少增加一倍，如果你離社團的層級為 $k$ 表示社團至少有 $2^k$ 個人，在總人數只有 $n$ 的前提下，層級不會超過 $\log(n)$。
做到這個方法，我們的併查集效率就會很不錯了，但還有另外一招來提高效率，這招數稱為**路徑壓縮**，做法是這樣：每當我們要做ifind()的時候，除了找到社長之外，我們”順便”把尋找過程中碰到的那些人的 $parent$ 直接改設成社團社長。這樣做似乎看不出直接的效果，事實上它是個**前人種樹後人乘涼**的概念，這次多花一點時間，但後續再做查找時，因為路徑都縮短了，就會比較快。這個效率的分析很不容易，基本上有人分析出，如果有一連串的合併與查詢，在以上這樣的方法之下，每一個操作所需要的均攤時間是 $O(\alpha(n))$，其中 $\alpha(n)$ 是 inverse Ackermann function，它是個成長及其緩慢的函數，所以幾乎可以當作是 $O(1)$ 看待，本單元中我們將以 $O(1)$ 來看待。詳細的分析這裡不多解釋，有興趣的讀者可以在網路上找到相關資料。以下我們透過一個例題來說明修改後的演算法。
[(題目連結) 684. Redundant Connection (Medium)](https://leetcode.com/problems/redundant-connection/)
題目說有一個圖，點的編號是1 ~ $n$，此圖是一個 tree 加上多一個邊，請找出一個邊，刪掉後剩下的圖是一個 tree。答案不唯一時找出最後出現的邊。
我們從沒有邊開始，逐次加入邊。每一個 connected component 的點視為同一個集合。一開始每個點自己是一個集合，每次加入一個邊 $(u,v)$ 時，就先檢查 $u,v$ 兩點是否已經屬於同一個集合，若是，我們就找到了所需要刪除的最後的邊，因為此邊加入會造成環路，違反 tree 的定義，且題目保證此圖只多一個邊。若兩端點不屬於同一個集合，我們就合併這兩個集合，相當於把此邊加入。
這個過程其實就是 Minimum Spanning Tree 的 Kruskal algorithm 的步驟。
以下是範例程式。第6 ~ 9行是$find()$，路徑壓縮通常是以遞迴的形式來寫，$parent[]$值是負的表示是 root (社長)，如果 $v$ 已經是 root，就直接回傳，否則求出 $parent[v]$ 的 root 並將自己的 $parent$ 直接設成 root，然後再回傳。
第10 ~ 16行是合併，這裡的寫法是假設傳入的 $u,v$ 都是 root 且不相等。我們會將小的集合併入大的，請留意 $parent[]$ 是存元素數量的負值，所以大小關係是顛倒的。
主程式方面，第19行一開始將每個點的 $parent$ 都設為$-1$，然後一一檢查輸入的邊 $(u,v)$，先找到各自所屬的集合(代表點) $ru$ 與 $rv$，如果找到的是同一點，表示兩點在同一個 componenet，也就找到答案了。否則將兩個集合合併。
時間複雜度 $O(n)$。
```python=
class Solution:
# dectecting the first edge resulting cycle
# union and find, No weighing rule takes 121 ms,
# add weighing rule
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
def find(v):
if parent[v]<0: return v
parent[v] = find(parent[v])
return parent[v]
def union(u,v): #weighing rule, u,v are roots
if parent[u]<parent[v]:
parent[u] += parent[v]
parent[v] = u
else:
parent[v] += parent[u]
parent[u] = v
n = len(edges) # also num of nodes
parent = [-1]*(n+1) # 1~n
for u,v in edges:
ru, rv = find(u),find(v)
if ru==rv: return [u,v]
union(ru,rv)
```
### Minimum Spanning Tree
Minimum Spanning Tree (MST)其實算是圖論中基本且重要的演算法，但LeetCode中很少屬於這類的題目，或者有一些像前面那題混在併查集中。我們在這裡還是說明一下MST的觀念與做法。
樹是沒有環路的連通圖，對於一個圖 $G$，它的一個生成樹(spanning tree)是指挑選 $G$ 的一些邊，將所有點連成一個連通區塊，而挑選的邊形成的是一個樹。因為 $n$ 個點至少要 $n-1$ 個邊才能形成一個連通區塊，而超過 $n-1$ 個邊必然會造成有環路，所以 spanning tree 一定恰好是 $n-1$ 個邊。$G$的最小生成樹(minimum spanning tree)是指邊的權重總和最小的生成樹。
假設我們有 $n$ 個城市，要建設一個交通網路將$n$ 個城市連起來，如果圖 $G$ 的每一個邊代表一條可以建設的道路，而邊上有一個非負的權重代表該道路的建設成本，那麼最小生成樹就是最低的建設總成本。下圖是一個例子，其中實線代表最小生成樹的邊，虛線代表沒有挑選的邊，圖中有8個點，一定剛好有7個邊。
計算最小生成樹有多個演算法，目前比較常用的有兩個：Prim演算法與Kruskal演算法。
先介紹Prim的演算法，這個演算法與Dijkstra演算法幾乎一模一樣，我們從任選一個點 $s$ 開始，逐步建構我們要的樹 $T$，每一回合會從尚未連進 $T$ 的點中挑選一個點 $v$ 以及一個已經在 $T$ 中的點$u$，將 $v$ 與邊 $(u,v)$ 加入 $T$ 中，而挑選的點與邊是滿足上面做法中成本最小的邊，也就是一點在 $T$ 中而另一點不在 $T$ 中的所有邊中，成本最小的邊。重複這個步驟直到全部的點都加入 $T$ 中為止。
Prim演算法與最短路徑的Dijkstra演算法只有比大小的key值不同，Dijkstra是起點走過來的總距離，而Prim則只看最後與parent相連的邊長。實作時需要與Dijkstra一樣使用PQ的技巧。
另外一個常用的是Kruskal演算法。這個做法也很簡單直覺，需要搭配的資料結構是併查集。演算法兩三句話就可以講完：將邊從小到大逐一考慮，如果一個邊加入不會形成環路就把它挑進來；否則將它捨棄。重複挑選邊直到沒有邊或者已經挑到 $n-1$ 個邊為止。
補充說明：因為要找出的邊數是固定值 $n$，所以把所有的邊同時加上一個值或減去一個值，答案的邊集合不會改變。因此，不管邊是正的或是負的，最小生成樹的找法都是一樣，此外，邊的總和最大的最大生成樹以及最大的邊最小的生成樹都可以用類似的方法計算。
## 範例說明
[(題目連結) 128. Longest Consecutive Sequence (Medium)](https://leetcode.com/problems/longest-consecutive-sequence/description/)
給一個整數陣列，要找到其中出現最長的連續整數，出現的位置無關。例如輸入$[100,4,200,1,3,2]$，答案是4，因為最長連續整數為$[1, 2, 3, 4]$，長度4。陣列長度$10^5$，數字範圍$-10^9$ ~ $10^9$。
本題要求$O(n)$時間複雜度，否則用sort後掃一遍應該不難解。數字範圍這麼廣又不能用排序，我們可以用Union-and-Find 中的概念。對於每個數字 $v$，如果他的前一個數字 $v-1$ 存在，我們將 $v-1$ 當成 $v$ 的 parent 看待，如果 $v-1$ 不存在，$v$ 就是這個區間的第一個。也就是說，我們把連續出現的整數看成同一個集合，代表元素是此區間的第一個整數。根據題目的要求，我們不必做出整個併查集，只要使用查詢的觀念來節省時間就好。
以下是範例程式。因為數字範圍很廣，我們需要用字典而不能像前面範例用list。我們用 $d[v]$ 表示 $v$ 結尾的連續整數長度。第5行的 $ifind$ 跟併查集中的查詢相同的概念，找到 $v-1$ 的長度後加一，紀錄在 $d[v]$ 後回傳。其中第7行檢查$d[v]$ 是否為0，目的是看看是否曾經計算過，只有未計算過的才會是0。這個程式可以說是併查集的路徑壓縮，也可以說是DP的 memoization。
時間複雜度$O(n)$。
範例程式後半部註解中，我們給了一個非遞迴的版本。
作法也很直接，如果是 $v-1$ 不存在，我們就往後一一檢查找到連續整數的尾巴。時間複雜度也是$O(n)$，因為只有區段的頭一個才會往下找。
```python=
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if not nums: return 0
d = {v:0 for v in nums}
def ifind(v,d):
if v not in d: return 0
if d[v]==0:
d[v] = ifind(v-1,d)+1
return d[v]
#
for v in nums:
ifind(v,d)
return max(d.values())
'''
another method without recursion
S = set(nums)
longest = 1
for v in nums:
if v-1 in S: continue
l = 1
while v+l in S:
l += 1
longest = max(longest, l)
return longest
'''
```
[(題目連結) 200. Number of Islands (Medium)](https://leetcode.com/problems/number-of-islands/description/)
方格圖(Grid)中有'1'或'0'，'1'表示土地，要找有幾個島嶼，也就是連通的'1'區塊。這題可以用BFS/DFS來做，這裡把它拿來示範併查集的做法。
這個是很標準的併查集做法，一開始讓每個土地各自一個集合，然後將相鄰的土地合併就好了。因為是方格圖，所以每個點以座標 $(r,c)$ 表示會稍微有點麻煩，做法不只一種，以下是範例程式。
我們第6 ~ 7行把右邊與下邊補'0'是當作邊界哨兵，省略邊界檢查。這裡的 $parent$ 用字典做。第9 ~ 20行是很標準的併查集，此處的點我們都用tuple $(row,column)$的形式。
第22行做初始，然後再一次雙迴圈，對每個'1'檢查他的下面與右邊，若也是'1'就做合併。
時間複雜度 $O(mn)$，也就是方格圖的大小的線性時間。
併查集寫起來會比BFS/DFS的程式碼略長。
```python=
class Solution:
# graph traversal or union and find
# using union and find
def numIslands(self, grid: List[List[str]]) -> int:
m,n = len(grid),len(grid[0])
for row in grid: row.append('0')
grid.append(['0']*n)
parent = {}
def find(v): # v=(row,col)
if parent[v]<(0,0): return v
parent[v] = find(parent[v])
return parent[v]
def union(u,v):
u = find(u); v = find(v)
if u==v: return
t = (parent[u][0]+parent[v][0],0)
if parent[u]>parent[v]: u,v = v,u
parent[v] = u
parent[u] = t
return
# initial set
for r in range(m):
for c in range(n):
if grid[r][c] == '1':
parent[r,c] = (-1,0)
for i in range(m):
for j in range(n):
if grid[i][j] != '1': continue
if grid[i+1][j] == '1':
union((i,j),(i+1,j))
if grid[i][j+1] == '1':
union((i,j),(i,j+1))
#
cnt = 0
for v in parent.values():
if v[0]<0: cnt += 1
return cnt
```
下面這題有點複雜。
[(題目連結) 803. Bricks Falling When Hit (Hard)](https://leetcode.com/problems/bricks-falling-when-hit/)
有一個 $m\times n$ 的方格圖，每一個位置如果是 1 表示磚塊，0 表示空格。磚塊如果透過磚塊連接到頂端的是**穩定**的，否則就會掉落消失，連通是指4方位相連。現在給你初始磚塊的分布以及一連串敲擊位置，每次敲擊如果該位置有磚塊，則會將該位置的磚塊敲碎消失，若此塊磚頭的消失使得其他磚塊變成**不穩定**，則不穩定的磚塊會掉落消失。請計算出每一次敲擊後，有多少個磚塊會掉落消失。
磚塊的聯通可以看成圖形的點形成連通區塊，計算連接到頂端的連通區塊就可以判斷哪些磚塊是穩定的。磚塊一個一個敲碎消失過程可以看成刪除圖形的點，當點消失時，連通區塊可能會被分割(分裂)成若干個。問題是如果決定敲碎磚塊的鄰居是否依然連通。
直接的做法每次敲碎磚塊時，對他的鄰居可以做一次走訪檢查是否仍有路徑相連。但是效率堪憂，一次走訪可以會花掉很多時間，我們可能有高達40000個敲擊。
這題的做法很經典，但是沒見過類似題型的人可能不容易自己想到。我們的併查集可以有效率的處理集合(圖形)合併的問題，但是沒有好的方法可以處理集合分割(分裂)。但是這些敲擊是一次給定所有的敲擊，我們可以**把敲擊的序列反過來做**。先把所有敲擊的磚塊移除，也就是所有敲擊完畢後的狀況，然後**逆著敲擊順序**，把敲擊的磚塊一一加回去，每加一個就用併查集做合併的動作。計算穩定的磚塊總數就可以知道敲落時有多少變成不穩定而消失。此法可以稱為**逆練併查集**，就像武俠小說中歐陽鋒逆練九陰真經。
以下是範例程式，程式有點長。每一個位置以$(row,column)$的tuple來表示，一開始我們掃一次 $hits$ 敲擊序列，將敲擊的位置改成0(空格)，並將原來的值保存在 $hits$ 的第三個元素，原因是可能敲在0或1的位置。(第5 ~ 8行)
我們用一個dummy node $(m,n)$ 來當作連到頂端的區塊的共同 root，這樣可以判斷穩定磚塊的個數，我們給他一個不可能大的點數，因為不希望在合併過程root 換人。(第9 ~ 12行)
第13 ~ 24行是併查集，此處合併時會先檢查傳入的兩個是否本來就屬同一集合，若是，則不必做。
第26 ~ 38行我們計算出初始狀態，也就是所有敲擊磚塊都消失後的連通區塊。我們以 $last$ 紀錄連通在頂端的穩定磚塊數量。
接著，依照敲擊的逆順序跑一個迴圈(第41行)，如果當時敲擊的是空格，就不必做(第42 ~ 44行)。否則，先將他自己設成一個單一點的區塊，也就是 $parent$ 設成$(-1,0)$，然後跟四個鄰居是 $1$ 的做合併，邊界要稍加留意。合併後查看連通到 root 的點數，差值就是因為敲擊而消失的磚塊數，扣掉敲擊的那一塊就是當時掉落消失的數量。(第46 ~ 53行)
時間複雜度$O(mn+len(hits))$，每一個動作的均攤都是$O(1)$。
```python=
class Solution:
def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
m,n,k = len(grid),len(grid[0]),len(hits)
result = []
for i in range(k):
r,c = hits[i]
hits[i].append(grid[r][c])
grid[r][c] = 0
root = (m,n) # dummy node connecting to all stable (row=0)
parent = {}
oo = -1000000
parent[root] = (oo,0) # make root always root
def find(v):
if parent[v]<(0,0): return v
parent[v] = find(parent[v])
return parent[v]
def union(u,v):
u = find(u); v = find(v)
if u == v: return
t = (parent[u][0]+parent[v][0],0)
if parent[u]>parent[v]: u,v=v,u
parent[v] = u
parent[u] = t
return
# initial component
for j in range(n):
if grid[0][j]:
parent[0,j] = (-1,0)
union((0,j),root)
for i in range(1,m):
if grid[i][0]:
parent[i,0] = (-1,0)
if grid[i-1][0]: union((i,0),(i-1,0))
for j in range(1,n):
if grid[i][j]:
parent[i,j]=(-1,0)
if j>0 and grid[i][j-1]: union((i,j),(i,j-1))
if grid[i-1][j]: union((i,j),(i-1,j))
#end initial component
last = parent[root][0]-oo # minus number of stable
for r,c,g in hits[::-1]: # reverse order
if g == 0:
result.append(0)
continue
parent[r,c] = (-1,0)
grid[r][c] = 1
if r == 0: union((r,c),root)
for nr,nc in ((r-1,c),(r,c-1),(r,c+1),(r+1,c)):
if 0<=nr<m and 0<=nc<n and grid[nr][nc]==1:
union((r,c),(nr,nc))
t = parent[root][0]-oo
if t < last: result.append(last-t-1)
else: result.append(0)
last = t
return result[::-1]
```
[(題目連結) 827. Making A Large Island (Hard)](https://leetcode.com/problems/making-a-large-island/)
有一個 $n\times n$ 的方格圖，每一個位置如果是1表示土地，0表示水。可以將一個0改成1，請問如此操作下可能產生的最大的島面積。
我們可以先將所有連通區塊求出來，對於每一個0的位置，計算如果該位置變成1時，所連到的1共有多少個。對於每一個1的位置，我們必須知道他所屬的連通區塊，這樣才不會重複計算。
計算連通區塊可以用併查集，但也可以用BFS/DFS來連通區塊。以下的範例程式，我們用DFS找出連通區塊，並將並將方格點的值改成其所屬的集合，因為原本的值只有0/1，我們的集合編號由2開始，另外用 $land$ 記錄每個集合的大小。(第4 ~ 13行)
第15 ~ 19行計算初始連通區塊，第22行開始，歷遍每一個0，把他4個鄰居的值(此時已經所屬集合編號)蒐集在一個集合中(集合避免重複)，然後計算大小總和。
時間複雜度$O(n^2)$，也就是線性時間。
這一題我們用了併查集的觀念，但是沒使用標準併查集，當然也可以用併查集來找初始連通區塊。
```python=
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
m,n = len(grid),len(grid[0])
land = [0,0] # start from 2
iland = 2
def dfs(r,c,root): #search a component and mark root
grid[r][c] = root
cnt = 1
for nr,nc in ((r-1,c),(r,c-1),(r,c+1),(r+1,c)):
if 0<=nr<m and 0<=nc<n and grid[nr][nc]==1:
grid[nr][nc]=root
cnt += dfs(nr,nc,root)
return cnt
# initial component
for i in range(m):
for j in range(n):
if grid[i][j]==1:
land.append(dfs(i,j,iland))
iland += 1
#end initial component
imax = 0
for r in range(m):
for c in range(n):
if grid[r][c]: continue
adj = set()
for nr,nc in ((r-1,c),(r,c-1),(r,c+1),(r+1,c)):
if 0<=nr<m and 0<=nc<n:
adj.add(grid[nr][nc])
t = 1+sum(land[x] for x in adj)
imax = max(imax,t)
if imax==0: imax=m*n
return imax
```
[(題目連結) 952. Largest Component Size by Common Factor (Hard)](https://leetcode.com/problems/largest-component-size-by-common-factor/)
給 $n$ 個不相同的正整數，每個數字看成圖的一個點，兩個數字若有大於1的公因數，則兩點之間有邊相連。請找出最大的連通區塊。$n\leq 20000$，數字不超過$R=10^5$。
如果可以把這個圖建起來，問題就簡單了，可以用併查集或是DFS來找連通區塊。但是我們不能把它建出來，因為邊的數量可能達到$O(n^2)$，例如全部都是偶數的情形。
我們可以從數字範圍 $R$ 下手。事實上這個圖是由一個二分圖定義的，二分圖的一邊是所有質數，另外一邊是輸入的數字，兩數字共有一個質因數則定義為相連。我們可以把需要的質數先找出來，把含有這個質數為因數的點都用併查集合併起來。但是找全部$\leq R$的質數還是有點大，我們可以把質數分成$\leq \sqrt{R}$的以及$> \sqrt{R}$的兩類來處理。
以下是範例程式。第5 ~ 18行是併查集，為了後面的方便，合併的時候我們回傳合併後的根結點。
第23行開始我們跑一個迴圈找出所有$\leq \sqrt{R}$的質數，同時，若 $p$ 是一個質數，我們就檢查陣列中所有的數，把 $p$ 的倍數全部蒐集起來，這些點都共有 $p$ 個這質因數，所以我們把它放在一個list $pset$中，這些找到的list都放在一個$hedge$中，將來做合併。不僅如此，在找到 $p$ 的倍數時，我們將 $p$ 從該數字中除掉(第31 ~ 32行)，目的是當$\leq \sqrt{R}$的質數全部處理完畢後，陣列中剩下的只有1或者是$> \sqrt{R}$的質數。
接著，第35 ~ 39行就來處理這些大質數，我們用字典蒐集剩下是相同質數的index，這些找到的list也都放入 $hedge$ 中。
然後第41行開始做合併的動作。對每一個 $hedge$ 中的list $pset$，我們要把 $pset$ 中的數字合併，所以先取出第一個$pset[0]$，然後把其他的與他合併，這裡稍微留意，兩集合合併後，root 可能會改變，所以我們的 union 要把合併後的 root 回傳。最後，答案在 $parent$ 中的最小值。
時間複雜度不太容易精準的計算，第23 ~ 33行跟質數篩檢有關。比較花時間的是每個質數要檢查整個陣列，所以與質數個數有關，但$\sqrt{10^5}$質數大概只有60個，此外，一個數字的質因數個數也是很小的數字，所以一個數字出現在 $hedge$ 中的總次數大概可以看成是線性的，在本題$R$不大的情況下。
```python=
class Solution:
# union and find
def largestComponentSize(self, nums: List[int]) -> int:
n = len(nums)
parent = [-1]*n
def ifind(y):
if parent[y]<0: return y
parent[y] = ifind(parent[y])
return parent[y]
def union(ru,rv): # different root
if parent[ru] < parent[rv]:
parent[ru] += parent[rv]
parent[rv] = ru
return ru
else:
parent[rv] += parent[ru]
parent[ru] = rv
return rv
# find prime factor
plimit = int(max(nums)**0.5)+1
isPrime = [True]*plimit
hedge = [] # hyper_edge connecting nodes
for p in range(2,plimit):
if not isPrime[p]: continue
for i in range(p+p,plimit,p):
isPrime[i] = False
pset = [] # set with factor p
for s in range(n):
if nums[s]%p==0:
pset.append(s)
while nums[s]%p==0:
nums[s] //= p
if len(pset)>=2: hedge.append(pset)
# prime and their multiple
d = defaultdict(list)
for i,p in enumerate(nums):
if p>1: d[p].append(i)
for pset in d.values():
if len(pset)>1: hedge.append(list(pset))
# union by hyper-edge
for pset in hedge:
root = ifind(pset[0])
for q in pset[1:]:
qr = ifind(q)
if qr == root: continue
root = union(root, qr)
#end for
return -min(parent)
```
[(題目連結) 1627. Graph Connectivity With Threshold (Hard)](https://leetcode.com/problems/graph-connectivity-with-threshold/)
與前一題有一點像，但比較簡單。題目說有個圖，點的編號是1 ~ $n$。給一個非負整數 $threshold$，兩點若有一個公因數$> threshold$，則兩點有邊相連。接著會給你若干個 $query$，每次詢問兩點是否有路徑相通。
兩點是否有路徑相通，也就是是否在同一個連通區塊。所以用併查集把連通區塊建起來就能回答 $query$了。因為要找公因數的數字固定是1 ~ $n$ 而非輸入進來的，所以處理起來比較簡單。
以下是範例程式。第3 ~ 4行是處理特判全部都有邊與全部都沒有邊的狀況。第5 ~ 21行是併查集。
主要的程式與質數篩檢很像，我們將檢查 $threshold+1$ ~ $n$ 的每一個數字 $i$，把 $i$ 的倍數都與 $i$ 合併起來(第23 ~ 27行)。
這樣做會太花時間，所以我們初始一個 $alive$，裡面都是True，將來 $i$ 如果有一個因數已經被檢查過了，就會被設為False，用以減少檢查的次數。因此在做 $i$ 的倍數時，會把倍數的 $alive$ 設為False(第27行)。
因為$1/2+1/3+\ldots 1/n = O(\log n)$，所以時間複雜度不會超過$O(n\log n)$，事實上會更好一點，因為與質數篩檢差不多，所以大概是$O(n\log \log n)$。
```python=
class Solution:
def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:
if threshold==0: return [True]*len(queries)
if threshold+threshold>=n: return [False]*len(queries)
parent = [-1]*(n+1)
def ifind(v):
if parent[v]<0: return v
parent[v] = ifind(parent[v])
return parent[v]
def union(v,u):
v = ifind(v)
u = ifind(u)
if u==v: return
t = parent[u]+parent[v]
if parent[u] < parent[v]:
parent[v] = u
parent[u] = t
else:
parent[u] = v
parent[v] = t
#end union and find
alive = [True]*(n+1)
for i in range(threshold+1,n+1):
if not alive[i]: continue
for j in range(i+i,n+1,i):
union(i,j)
alive[j] = False
ans = [ifind(u)==ifind(v) for u,v in queries]
return ans
```
[(題目連結) 1697. Checking Existence of Edge Length Limited Paths (Hard)](https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths/)
給一個無向圖的邊集合，邊上有長度。要回答多個查詢 $queries[j] = [p_j, q_j, limit_j]$，每個查詢是問：點 $p_j$ 與 $q_j$ 之間是否存在一條路徑且此路徑的每個邊長度都小於 $limit_j$。
我們把查詢依照邊的長度限制 $limit_j$ 排序，把$< limit_j$的邊用併查集加入，查詢兩點是否在同一個連通區塊，就知道是否存在路徑。
以下是範例程式。第4行初始將所有的邊依照長度排序，後面加個不存在無限大的邊是當作哨兵。
第6 ~ 18行是併查集。第21行開始的迴圈每次處理一個查詢，依照長度限制由小到大，但要能夠知道是原來的第 $i$ 個查詢，以便擺放答案。用while迴圈將小於限制的邊都加入後，檢查兩點是否同一個連通區塊即可。
時間複雜度$O(n+m\log m+q\log q)$，$n,m$是點數與邊數，$q$是查詢數。
```python=
class Solution:
# union and find
def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:
edgeList.sort(key=lambda x: x[2])
edgeList.append([-1,-1,1000000001])
p = [-1]*n # parent
def find(v):
if p[v]<0: return v
p[v] = find(p[v])
return p[v]
def union(u,v):
u,v = find(u),find(v)
if u==v: return
t = p[u]+p[v]
if p[u] > p[v]: u,v = v,u
p[v] = u
p[u] = t
# end
ans = [False]*len(queries)
ie = 0 # index of edge
for l,i in sorted([(x[2],i) for i,x in enumerate(queries)] ): # sorted by lim
while edgeList[ie][2] < l:
union(edgeList[ie][0],edgeList[ie][1])
ie += 1
if find(queries[i][0]) == find(queries[i][1]):
ans[i] = True
return ans
```
[(題目連結) 1970. Last Day Where You Can Still Cross (Hard)](https://leetcode.com/problems/last-day-where-you-can-still-cross/)
有一個矩陣，0代表土地，1代表水。一開始全部都是土地，每天有一格會變成水，請找出最後一天還能從最上一列的任何一格走到最下面一列的任何一格。
這題也是**逆練併查集**的題目，我們把變成水的順序逆過來，看成從全部都是水，每天有一格變成土地，找出第一天可以從第一列走到最後一列。
以下是範例程式。第3 ~ 6行初始時加入一個dummy的top 與 bot 表示最前與最後一列的 parent，本題parent 用字典做。第7 ~ 15行是併查集，本題我們沒有用 weighting rule，也就是合併時沒有一定把小的併給大的，而是固定把後面併給前面。
第18行開始每次處理逆轉順序的一格變成1，檢查四周鄰居，如果沒有出界且是1就做合併(第21 ~ 23行)。對於第一列與最後一列在第24 ~ 25行特別處理，然後查一下頭尾是否在同一個區塊。
因為我們沒有使用 weighting rule，只用了路徑壓縮，時間複雜度最壞時多一個log，是$O(mn\log(mn))$，其中$m,n$是列數與行數。
```python=
class Solution:
def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
top,bot = (0,0),(row+1,0)
parent = {}
parent[top] = top
parent[bot] = bot
def ifind(v):
if parent[v]==v: return v
parent[v] = ifind(parent[v])
return parent[v]
def union(v,u):
v = ifind(v)
u = ifind(u)
if u==v: return
parent[u] = v
#end union and find
step = row*col-1
for r,c in cells[::-1]:
v = (r,c)
parent[v] = v
for nr,nc in ((r-1,c),(r,c-1),(r,c+1),(r+1,c)):
if 1<=nr<=row and 1<=nc<=col and (nr,nc) in parent:
union(v,(nr,nc))
if r==1: union(top,v)
if r==row: union(bot,v)
if ifind(top)==ifind(bot): return step
step -= 1
return -1
```
下面一題是個Minimum spanning tree的問題。
[(題目連結) 1584. Min Cost to Connect All Points (Medium)](https://leetcode.com/problems/min-cost-to-connect-all-points/)
給$n$個平面上的點座標，要在這些點之間建立連線，請問使得全部的點連通的最少成本，兩點之間連線的成本以manhattan distance計算，也就是$|x_i - x_j| + |y_i - y_j|$。
看成 $n$ 個點的圖，任兩點之間都有邊，要求MST。我們用 Prim algorithm 來做，因為是 Dense graph，也不需要 heap。用一個 list 紀錄每個點加入的成本，本次選出最小成本的點就可以了。
以下是範例程式。第6 ~ 7行定義一個函數計算兩點的成本。我們以0為開始的點，第8行cost是每個點加入的成本，已加入的點會以oo表示。第10行開始迴圈，每次加入一點，要做 $n-1$ 次。每次先計算cost的最小值，然後找到最小值的點 $v$，若有相同，我們就找第一個最小值。然後用一個迴圈更新尚未加入點的成本。
時間複雜度$O(n^2)$。
```python=
class Solution:
# MST O(n^2) Prim algorithm
def minCostConnectPoints(self, points: List[List[int]]) -> int:
n = len(points)
oo = 5000000
def leng(i,j):
return abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])
cost = [oo]+[leng(0,i) for i in range(1,n)]
total = 0
for it in range(n-1):
mincost = min(cost)
v = cost.index(mincost)
total += mincost
for i in range(n):
if cost[i] < oo:
cost[i] = min(cost[i],leng(v,i))
cost[v] = oo
return total
```
下面這題是有點難的題目。
[(題目連結) 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree (Hard)](https://leetcode.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/)
給一個邊上有長度的無向圖。要找出下面兩種邊：
* Critical edge：一個邊若刪除後會導致minimum spanning tree(MST)的cost增加，則稱為critical edge。
* Pseudo-critical edge：一個edge會出現在某個MST中，但不是出現在所有MST中。
Critical edge就是任何MST都會包含的邊。我們可以用Kruskal algroithm來想這個問題。首先，如果每個邊的長度都是不一樣的，MST是唯一的，因為在Kruskal演算法運作中，一個邊不是被選入就是被丟棄。所以，只要使用Kruskal就可以判斷出那些邊是critical，那些不是。
但是在有相同長度邊時，這個問題就比較複雜了。
我們從小到大加入邊，維護好目前的連通區塊。每次考慮目前邊長是最小值的所有邊，此時小於此邊長的邊都以加入或丟棄。
* 如果一個邊的兩端是同一個連通區塊，這個邊是要丟棄的。
* 其他的邊是critical或pseudo-critical。想像每個連通區塊是一個點，剩下這些邊是跨在這些連通區塊的邊，一個邊如果是在環路上，則是可以被取代的，也就是pseudo-critical；否則，這個邊是Bridge，就是critical。
以下是範例程式。第4行先將邊依照邊長排序，但要記住原來的編號。第6 ~ 21行是併查集。第23 ~ 44行是傳入一組相同邊長的邊，檢查那些是bridge。檢查bridge其實是有比較快的演算法，但這裡的邊數不多，我們就對每一根邊做一次BFS，檢查是否有不用此edge的path就可以了，時間複雜度是$O(mn)$。第46行開始是主程式，我們歷遍所有排序好的邊，每次蒐集一組邊長相同的邊，先丟棄不需要的邊，剩下的傳給副程式bridge做檢查。
完整的時間複雜度是$O(m\log m + mn)$。本題$n\leq 100$, $m\leq 200$。
```python=
class Solution:
# consider all edges of the same weight
def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
edge = sorted([[e[2],e[0],e[1],i] for i,e in enumerate(edges)])
ans = [[],[]]
parent = [-1]*n # parent for union and find
def ifind(v):
if parent[v]<0: return v
parent[v] = ifind(parent[v])
return parent[v]
def union(v,u):
v = ifind(v)
u = ifind(u)
if u==v: return
t = parent[u]+parent[v]
if parent[u] < parent[v]:
parent[v] = u
parent[u] = t
else:
parent[u] = v
parent[v] = t
#end union and find
def bridge(e): # return critical and pseudo_critical
adj = defaultdict(list)
for u,v,idx in e:
adj[u].append(v) # adj to vertex via edge
adj[v].append(u)
e1,e2 = [],[]
for u,v,idx in e: #enumerate and check
if adj[u].count(v)>1:
e2.append(idx)
continue
#bfs to find path u to v
que = [s for s in adj[u] if s!=v];head=0
visit = set(que)|{u}
while head<len(que) and v not in visit:
r =que[head]; head += 1
for s in adj[r]:
if s not in visit:
que.append(s)
visit.add(s)
if v in visit: e2.append(idx)
else: e1.append(idx)
return e1,e2
#end bridge
i = 0
while i<len(edge):
j = i+1
while j<len(edge) and edge[j][0]==edge[i][0]:
j += 1
# edge[i:j] of same weight
f = []
for w,u,v,idx in edge[i:j]:
u = ifind(u); v=ifind(v)
if u!=v: f.append([u,v,idx])
f1,f2 = bridge(f)
ans[0] += f1; ans[1]+=f2
# construct mst
for u,v,idx in f:
union(u,v)
i = j
#end while
return ans
```
## 結語
併查集
併查集是個重要的資料結構，應用也很多，在歷史上發展的很早，在西元1964年就已經被提出，背後的分析比較難，晚了很多年經過一些學者的努力才被完整證明出來。雖然分析不易，但寫法簡單且效率高。
很多問題存在併查集與BFS/DFS都可以的解法。併查集的題目通常蠻容易看出來的，但要注意逆練併查集那一類的題目。
Sign in with Wallet
Connect another wallet