preface
并查集，通常用于处理动态 联通性 的问题
- 基本操作
- 查询 Find
- 合并 Union
- 基本思想
- 代表元
- 路径压缩
- 解题模板：
f = {}
def find(x):
f.setdefault(x, x)
while x != f[x]:
f[x] = f[f[x]]
x = f[x]
return x
def union(x, y):
f[find(x)] = find(y)
基础题目
990. 等式方程的可满足性
思路：普通并查集
class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
f = {}
def find(x):
f.setdefault(x,x)
while x!=f[x]:
f[x] = f[f[x]]
x = f[x]
return x
def union(x,y):
f[find(x)] = find(y)
for e in equations:
a,b,c,d = tuple(e)
if b=="=":
union(a,d)
for e in equations:
a,b,c,d = tuple(e)
if b == "!":
if find(a)==find(d):
return False
return True
547. 省份数量
思路：普通并查集
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n = len(isConnected)
ans = n
f = {}
def find(x):
f.setdefault(x, x)
while x != f[x]:
f[x] = f[f[x]]
x = f[x]
return x
def union(x,y):
f[find(x)] = f[y]
for x in range(n):
for y in range(n):
if isConnected[x][y] and find(x)!=find(y):
union(x,y)
ans -= 1
return ans
684. 冗余连接
思路：逐边连接，若发现边的两个点是同一个根，则会连成环
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
f = {}
def find(x):
f.setdefault(x, x)
while x != f[x]:
f[x] = f[f[x]]
x = f[x]
return x
def union(x, y):
f[find(x)] = find(y)
for x,y in edges:
if find(x) == find(y):
return [x, y]
union(x, y)
1319. 连通网络的操作次数
思路：普通并查集
class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
m = len(connections) #线缆数
if n > m+1: return -1
f = {}
res = n-1
def find(x):
f.setdefault(x, x)
while x != f[x]:
f[x] = f[f[x]]
x = f[x]
return x
def union(x, y):
f[find(x)] = find(y)
for x,y in connections:
if find(x)!=find(y):
union(x, y)
res -= 1
return res
765. 情侣牵手
题意化简抽象的过程，有些复杂。。。
class Solution:
def minSwapsCouples(self, row: List[int]) -> int:
n = len(row)//2 # 情侣对数
f = {} # uf模板
def find(x):
f.setdefault(x, x)
while x != f[x]:
f[x] = f[f[x]]
x = f[x]
return x
def union(x, y):
f[find(x)] = find(y)
cnt = n # 联通分量，每个点代表一对情侣
for i in range(0,n*2,2):
if find(row[i]//2) != find(row[i+1]//2): #不是一对（一堆）
union(row[i]//2, row[i+1]//2)
cnt -= 1
return n-cnt
这题暴力也行…
class Solution:
def minSwapsCouples(self, row: List[int]) -> int: # 暴力解，异或运算
result = 0
for i in range(0, len(row), 2):
if row[i] == row[i + 1] ^ 1: # 运用异或运算判断是不是一对情侣
continue
for j in range(i + 2, len(row), 1): # 如果不是，再进行搜寻
if row[j] ^ 1 == row[i]: # 搜到了，那么接下来进行座位交换
row[i + 1], row[j] = row[j], row[i + 1]
result += 1 # 交换次数+1
break
return result # 得到总的交换次数
进阶题目
99. 除法求值
并查集的同时维护变量间的倍数关系
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
f = {} #记录每个结点的root
d = {} #记录每个结点到root的权
def find(x): #找到x的根节点并整理
f.setdefault(x, x)
d.setdefault(x,1)
if x != f[x]:
t = f[x]
f[x] = find(t)
d[x] *= d[t]
return f[x]
return x
def union(x, y, value):
a, b = find(x), find(y)
if a != b:
f[a] = b # a 的根结点是b
d[a] = d[y] / d[x] * value # a在b树上的权
def check(x, y):
if x not in f or y not in f:
return -1.0
a, b = find(x), find(y)
if a != b: return -1.0 #ab不在一棵树
return d[x] / d[y]
for (x,y),v in zip(equations,values):
union(x, y, v)
return [check(x,y) for x,y in queries]
#不太懂啊。。。
DFS 会简单些
959. 由斜杠划分区域
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
n = len(grid)
cnt = n*n*4
f = {}
def find(x):
f.setdefault(x, x)
while x != f[x]:
f[x] = f[f[x]]
x = f[x]
return x
def union (x, y):
nonlocal cnt
if find(x) != find(y):
f[find(x)] = find(y)
cnt -= 1
def get_pos(row,col,i):
return (row*n+col)*4+i
for i in range(n):
for j in range(n):
v=grid[i][j]
if j>0:
union(get_pos(i,j-1,1),get_pos(i,j,3))
if i>0:
union(get_pos(i-1,j,2),get_pos(i,j,0))
if v=='/':
union(get_pos(i,j,0),get_pos(i,j,3))
union(get_pos(i,j,1),get_pos(i,j,2))
elif v=='\\':
union(get_pos(i,j,0),get_pos(i,j,1))
union(get_pos(i,j,2),get_pos(i,j,3))
else:
union(get_pos(i,j,0),get_pos(i,j,1))
union(get_pos(i,j,2),get_pos(i,j,3))
union(get_pos(i,j,1),get_pos(i,j,2))
return cnt
778. 水位上升的泳池中游泳
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
f = {} #并查集板子
def find(x):
f.setdefault(x, x)
while x != f[x]:
f[x] = f[f[x]]
x = f[x]
return x
def union(x, y):
f[find(x)] = find(y)
rows, cols = len(grid), len(grid[0]) #准备工作
edges = []
for i in range(rows):
for j in range(cols):
idx = i*cols + j
if i:
edges.append([idx,idx-cols,max(grid[i][j],grid[i-1][j])])
if j:
edges.append([idx, idx-1, max(grid[i][j],grid[i][j-1])])
edges.sort(key = lambda x:x[2])
res = 0
for x,y,w in edges: #从最小花费边处理
if find(x) == find(y):
continue
union(x,y)
res = w
if find(0) == find(rows*cols-1):
break
return res
1202. 交换字符串中的元素
class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
f = {} #并查集板子
def find(x):
f.setdefault(x, x)
while x != f[x]:
f[x] = f[f[x]]
x = f[x]
return x
def union(x, y):
f[find(x)] = find(y)
for x,y in pairs:
union(x,y)
d = defaultdict(list) #建立顺序关系
for i in range(len(s)):
d[find(i)].append(i)
#print(d)
res = list(s) #开始处理
for arr in d.values():
target = sorted(arr, key = lambda x:s[x])
for i,j in zip(arr,target):
res[i] = s[j]
return "".join(res)
947. 移除最多的同行或同列石头
最多可以移除的石头的个数 = 所有石头的个数 - 连通分量的个数。
# x 坐标，编号为 x 点
# y 坐标，编号为 10001 + y 点
# 对每个坐标开始联通
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
f = {} #并查集板子
def find(x):
f.setdefault(x, x)
while x != f[x]:
f[x] = f[f[x]]
x = f[x]
return x
def union(x, y):
f[find(x)] = find(y)
for x,y in stones:
union(x, 10001+y)
return len(stones) - len({find(x) for x,y in stones})
803. 打砖块
参考资料：
- 算法笔记（并查集）：https://zhuanlan.zhihu.com/p/93647900
