主要內容：并查集

并查集

并查集的題目感覺大部分都是模板題，上板子！！

class UnionFind:def __init__(self, n):self.pa = list(range(n))self.size = [1]*n self.cnt = ndef find(self, x):if self.pa[x] != x:self.pa[x] = self.find(self.pa[x])return self.pa[x]def merge(self, x, y):fx = self.find(x)fy = self.find(y)if fx == fy:return Falseself.pa[fx] = fy self.size[fy] += self.size[fx]self.cnt -= 1return True def is_same(self, x, y):return self.find(x) == self.find(y)

merge函數用于判斷x,y是否聯通，如果聯通return False。

lanqiao19719吊墜

# 并查集模板
class UnionFind:def __init__(self, n):self.pa = list(range(n))self.size = [1]*n self.cnt = ndef find(self, x):if self.pa[x] != x:self.pa[x] = self.find(self.pa[x])return self.pa[x]def merge(self, x, y):fx = self.find(x)fy = self.find(y)if fx == fy:return Falseself.pa[fx] = fy self.size[fy] += self.size[fx]self.cnt -= 1return True def is_same(self, x, y):return self.find(x) == self.find(y)n, m = map(int, input().split()) # 輸入處理strings = [] # 記錄字符串
for _ in range(n):strings.append(input())# 邊權為這兩個字符串的最長公共子串的長度,可以按環形旋轉改變起始位置，但不能翻轉
def f(s):m = len(s)# 兩個字符串拼接起來s_concat = s + s # 字典，鍵為子串長度，值為子串suffix_dict = {}for i in range(m):rotated = s_concat[i:i+m]for k in range(1, m):# 旋轉之后的子串suffix = rotated[-k:]if k not in suffix_dict:suffix_dict[k] = set()suffix_dict[k].add(suffix)return suffix_dict suffix_dicts = []
for s in strings:suffix_dicts.append(f(s))# 建圖，包括邊權，連接點
edges = []
for i in range(n):for j in range(i+1, n):max_ij_k = 0 for k in range(m, -1, -1):suffix_set_i = suffix_dicts[i].get(k, set())suffix_set_j = suffix_dicts[j].get(k, set())# 如果兩個集合相交不為空，記錄max_ij_k為k，因為是逆序的，所以直接記錄并breakif suffix_set_i & suffix_set_j:max_ij_k = k break weight = max_ij_kedges.append((weight, i, j))
# 邊權從小到大排序
edges.sort(reverse=True, key=lambda x : x[0])
uf = UnionFind(n)
# ans記錄值，cnt記錄次數
ans = 0 
cnt = 0
for weight, i, j in edges:if uf.merge(i, j):ans += weightcnt += 1# 臨界if cnt == n-1:break 
print(ans)

3493. 屬性圖

class UnionFind:def __init__(self, n):self.pa = list(range(n))self.size = [1]* n self.cnt = n def find(self, x):if self.pa[x] != x:self.pa[x] = self.find(self.pa[x])return self.pa[x]def merge(self, x, y):fx = self.find(x)fy = self.find(y)if fx == fy:return False self.pa[fx] = fy self.size[fy] += self.size[fx]self.cnt -= 1return True def is_same(self, x, y):return self.find(x) == self.find(y)class Solution:def numberOfComponents(self, properties: List[List[int]], k: int) -> int:sets = list(map(set, properties))uf = UnionFind(len(properties))for i, a in enumerate(sets):for j, b in enumerate(sets[:i]):if len(a&b) >= k:uf.merge(i, j)return uf.cnt

思路：并查集，先利用集合的特性去重，根據properties的長度實例化并查集，雙重循環得到集合a和集合b，根據題目要求當?intersect(properties[i], properties[j]) >= k（其中?i?和?j?的范圍為?[0, n - 1]?且?i != j），節點?i?和節點?j?之間有一條邊，即當滿足條件時，將i，j連起來，并在merge函數中self.cnt -= 1。最終返回uf.cnt就行。

1971. 尋找圖中是否存在路徑

class UnionFind:def __init__(self, n):self.pa = list(range(n))self.size = [1]*n self.cnt = ndef find(self, x):if self.pa[x] != x:self.pa[x] = self.find(self.pa[x])return self.pa[x]def merge(self, x, y):fx = self.find(x)fy = self.find(y)if fx == fy:return Falseself.pa[fx] = fy self.size[fy] += self.size[fx]self.cnt -= 1return True def is_same(self, x, y):return self.find(x) == self.find(y)class Solution:def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:uf = UnionFind(n)for i, j in edges:uf.merge(i, j)return uf.is_same(source, destination)

實例化一個并查集，遍歷edges中的i,j并連起來，遍歷結束就使用is_same()函數進行判斷是否連在一起。

200. 島嶼數量

class UnionFind:def __init__(self, n):self.pa = list(range(n))self.size = [1]*n self.cnt = ndef find(self, x):if self.pa[x] != x:self.pa[x] = self.find(self.pa[x])return self.pa[x]def merge(self, x, y):fx = self.find(x)fy = self.find(y)if fx == fy:return Falseself.pa[fx] = fy self.size[fy] += self.size[fx]self.cnt -= 1return True def is_same(self, x, y):return self.find(x) == self.find(y)class Solution:def numIslands(self, grid: List[List[str]]) -> int:n = len(grid)m = len(grid[0])uf = UnionFind(m*n)ocean = 0for i in range(n):for j in range(m):if grid[i][j] == "0":ocean += 1else:# 向下查看if i < n-1 and grid[i+1][j] == "1":uf.merge(i*m+j, (i+1)*m+j)# 向右查看if j < m-1 and grid[i][j+1] == "1":uf.merge(i*m+j, i*m+j+1)return uf.cnt - ocean

思路：獲得grid的高n寬m，通過n*m實例化并查集，將grid中的每個元素當作一個點看，然后使用ocean記錄海水的熟練，當grid[i][j]==“1”時，向下向右查看，如果下面是1將當前位置i*m+j和(i+1)*m+j連起來，當右邊是1將當前位置和i*m+j+1連起來。最終返回uf.cnt-ocean即為所求答案。

1631. 最小體力消耗路徑

class UnionFind:def __init__(self, n):self.pa = list(range(n))self.size = [1]* n self.cnt = n def find(self, x):if self.pa[x] != x:self.pa[x] = self.find(self.pa[x])return self.pa[x]def merge(self, x, y):fx = self.find(x)fy = self.find(y)if fx == fy:return False self.pa[fx] = fy self.size[fy] += self.size[fx]self.cnt -= 1return True def is_same(self, x, y):return self.find(x) == self.find(y)class Solution:def minimumEffortPath(self, heights: List[List[int]]) -> int:n = len(heights)m = len(heights[0])uf = UnionFind(n*m)edges = []dirs = (0, 1, 0)for i in range(n):for j in range(m):for a, b in pairwise(dirs):x = i + ay = j + b if 0 <= x < n and 0 <= y < m:edges.append((abs(heights[i][j] - heights[x][y]), i*m+j, x*m+y))edges.sort() # 求最小for h, i, j in edges:uf.merge(i, j)if uf.is_same(0, m*n-1):return h return 0

思路：和島嶼數量思路類似，通過n*m實例化并查集，edges記錄i，j和x,y之間的高度之差絕對值。根據這個值進行排序edges，然后開始遍歷edges，每次遍歷將i,j連起來，并判斷起點0和m*n-1是否連起來了，連起來了就直接return h因為edges是在此之前排過序的。

924. 盡量減少惡意軟件的傳播

class UnionFind:def __init__(self, n):self.pa = list(range(n))self.size = [1]* n self.cnt = n def find(self, x):if self.pa[x] != x:self.pa[x] = self.find(self.pa[x])return self.pa[x]def merge(self, x, y):fx = self.find(x)fy = self.find(y)if fx == fy:return False self.pa[fx] = fy self.size[fy] += self.size[fx]self.cnt -= 1return True def is_same(self, x, y):return self.find(x) == self.find(y)class Solution:def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:n = len(graph)m = len(graph[0])uf = UnionFind(n)for i in range(n):for j in range(i + 1, n):graph[i][j] and uf.merge(i, j)cnt = Counter(uf.find(x) for x in initial)ans, mx = n, 0for x in initial:root = uf.find(x)if cnt[root] > 1:continuesz = uf.size[root]if sz > mx or (sz == mx and x < ans):ans = xmx = szreturn min(initial) if ans == n else ans