每次刷到并查集（DSU）算法題将在此博文更新~~~
🚀關于并查集的資料請看以下2個連結：
1.什麼是并查集？
2.【圖解】遇到就深究——并查集
并查集是一種樹型的資料結構，用于處理一些不相交集合（disjoint sets）的合并及查詢問題。
🚀以下為DSU的python簡單實作（關于DSU的find部分和union部分的優化可以看上面：連結2）
class DSU:
def __init__(self, nums):
self.parent = {num: num for num in nums}
def find(self, x):
while x != self.parent[x]:
self.parent[x] = self.parent[self.parent[x]] #加一句這個可以壓縮優化路徑（不加也沒錯）
x = self.parent[x]
return x
def union(self, x, y):
# 查
root1, root2 = self.find(x), self.find(y)
# 并
# 根已經相同 就不需要合并了
if root1 == root2: return
# 根不同，則将一個根節點降級為子節點，連到另一個根結點上
self.parent[root2]=root1
| 難度 | 題目 |
|---|---|
| 中等 | 最長連續序列 |
| 中等 | 統計子島嶼 |
| 中等 | 由斜杠劃分區域 |
| 困難 | 情侶牽手 |
⭐統計子島嶼：
看完題目，首先想到的是把grid2内的所有島嶼找出來（即DSU得到的1的連通分量個數），然後再判斷這些連通塊是否都在grid1内，想了想如果這樣還要把每個連通分量存起來後面再周遊判斷是否在grid1中，丢。。好像挺麻煩。
然後再想，在grid1中為0并且在grid2中為1的陸地全置為0（我通過BFS周遊來置0），再用DSU去求grid2中1的連通分量個數不就是題目要求的子島嶼數目了？
沖了一波BFS+DSU，最後送出時間上超越96%使用者，空間上超越64%使用者。
import collections
class DSU:
def __init__(self, nums):
self.parent = {i: i for i in range(nums)}
self.cc = nums #最大連通分量
def find(self, x):
while x != self.parent[x]:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, x, y):
rootx, rooty = self.find(x), self.find(y)
if rootx == rooty: return
self.parent[rooty] = rootx
self.cc -= 1
class Solution:
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
nrow = len(grid1)
ncol = len(grid1[0])
#----------------------BFS走起------------------------------
queue = collections.deque()
for i in range(nrow):
for j in range(ncol):
if grid1[i][j]==0 and grid2[i][j]==1:
grid2[i][j]=0
queue.append((i,j))
while queue:
x, y = queue.popleft()
for tx,ty in [(x-1,y), (x+1,y), (x,y-1), (x,y+1)]:
if 0<=tx<nrow and 0<=ty<ncol and grid2[tx][ty]==1:
grid2[tx][ty] = 0
queue.append((tx, ty))
#---------------------------------------------------------
#----------------------DSU走起------------------------------
dsu = DSU(nrow*ncol)
num0 = 0 #記錄那些0的個數，因為一個0單獨是一個連通分量，DSU合并隻是将連通的1進行了合并
for i in range(nrow):
for j in range(ncol):
idx = i*ncol + j #因為對每個格子按0，1，2，...編号了，友善合并的寫法
if grid2[i][j] == 1:
if j+1<ncol and grid2[i][j+1]==1: #向右合并，因為題目要求水準垂直方向
dsu.union(idx, idx+1)
if i+1<nrow and grid2[i+1][j]==1:#向下合并，因為題目要求水準垂直方向
dsu.union(idx, idx+ncol)
else: num0 += 1
#---------------------------------------------------------
return dsu.cc-num0 #把單獨的連通分量0減掉
⭐由斜杠劃分區域：
這題關鍵就是将每個1x1單元格拆分成4個三角形按順序編上号，然後用DSU按如下單元格内、單元格間的合并方式進行合并，如下：
class DSU:
def __init__(self, nums):
self.parent = {i: i for i in range(nums)}
self.cc = nums #最大連通分量個數即每個1x1單元格由/、\構成（即包含4個三角形）
def find(self, x):
while x!= self.parent[x]:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, x, y):
rootx, rooty = self.find(x), self.find(y)
if rootx == rooty: return
self.parent[rooty] = rootx
self.cc -= 1 #每連接配接一次，最大連通分量個數就減1
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
N = len(grid)
nums = 4*N*N
dsu = DSU(nums)
for i in range(N):
for j in range(N):
idx = 4*(i*N+j)
#------------判斷1*1格内的連通---------------
if grid[i][j] == '\\':
dsu.union(idx, idx+1)
dsu.union(idx+2, idx+3)
elif grid[i][j] == '/':
dsu.union(idx, idx+3)
dsu.union(idx+1, idx+2)
else:
dsu.union(idx, idx+1)
dsu.union(idx+1, idx+2)
dsu.union(idx+2, idx+3)
#----------------------------------------------
#------------連通1*1方格的右、下1*1方格---------------
if j+1<N:#連通右邊的1*1方格
dsu.union(idx+1, idx+7)
if i+1<N:#連通下邊的1*1方格
dsu.union(idx+2, idx+4*N)
#----------------------------------------------
return dsu.cc
⭐最長連續序列：
法1：
首先想到的是先排序，然後根據相鄰兩元素是否相差1，用個變量記錄最大序列長度。這裡主要的時間複雜度是排序算法的時間複雜度。
法2 （DSU）：
import collections
class DSU:
def __init__(self, nums):
self.parent = {num: num for num in nums}
self.cnt = collections.defaultdict(lambda: 1)
def find(self, x):
while x != self.parent[x]:
x = self.parent[x]
return x
def union(self, x, y):
#直接return最小值1即可，沒必要return self.cnt[self.find(x)]浪費時間查找
#因為前面max_length會記錄最大序列長度
if y not in self.parent: return 1
root1, root2 = self.find(x), self.find(y)
if root1 == root2: return self.cnt[root1]
self.parent[root2] = root1 #這個root, root1位置可以使最小元素為根節點，有利于查找
self.cnt[root1] += self.cnt[root2]
return self.cnt[root1]
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if len(nums)==0: return 0
dsu = DSU(nums)
max_length = 1
for num in nums:
#本題要找連續序列，數字的連續就是上一個元素和下一個元素差1
max_length = max(max_length, dsu.union(num, num+1))
return max_length
法3：
還有一種簡單方法：
對于一個數x，考慮以其為起點，不斷嘗試比對 x+1, x+2⋯ 是否存在，用一個變量記錄最大比對長度。
外層循環需要 O(n)時間複雜度，隻有當一個數是連續序列的第一個數的情況下才會進入内層循環，然後在内層循環中比對連續序列中的數，是以數組中的每個數隻會進入内層循環一次。是以總時間複雜度為 O(n)。
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
max_len = 0
nums_set = set(nums) #去重
for num in nums_set:
#判斷是否連上，連上說明剛才枚舉計算過了
if num-1 not in nums_set:
current_len = 1
#枚舉
while num+1 in nums_set:
num += 1
current_len += 1
max_len = max(max_len, current_len)
return max_len
⭐情侶牽手：
這題的關鍵就是：
1.有N_lovers對情侶最大就有N_lovers對連通分量。
2.坐對位置的情侶，它們的編号除2是相等的：row[i]//2 == row[i+1]//2
3.将坐錯位置的情侶 并且！！！互相之間需要配合調換位置的情侶們連在一起：
如下，用相同符号代表情侶，可知，虛線左部分5對情侶至少需要互相配合調換位置（5-1）次，虛線右部分2對情侶至少需要互相配合調換位置（2-1）次。
由此可知，n對需要互相配合調換位置的情侶，至少需要調換位置（n-1）次。
是以有K個連通分量（所有連通分量的情侶對數之和為N_lovers）的話，那總的至少需要調換位置次數為:
（連通分量1的情侶數-1）+。。。+（連通分量K的情侶數-1）= N_lovers - K
class DSU:
def __init__(self,N_lovers):
self.parent = {i: i for i in range(N_lovers)}
self.cc = N_lovers # connected components:最大連通分量
def find(self,x):
while x != self.parent[x]:
x = self.parent[x]
return x
def union(self,x,y):
rootx, rooty = self.find(x), self.find(y)
#把坐對位置的情侶單獨算一個連通分量
if rootx==rooty:
return
#将坐錯位置的情侶 并且！！！互相之間需要配合調換位置的情侶們堆在一起，
#每連一條線就少一個連通分量（因為如果坐對位置，一對情侶就是一個連通分量）
self.parent[rooty] = rootx
self.cc -= 1
class Solution:
def minSwapsCouples(self, row: List[int]) -> int:
N_people = len(row)
N_lovers = N_people//2
if N_lovers==1: return 1
dsu = DSU(N_lovers)
for i in range(0,N_people,2):
dsu.union(row[i]//2, row[i+1]//2)
#最大連通分量個數-真實剩餘的連通分量個數
return N_lovers-dsu.cc