目录
Union-Find算法
简介
Union Find算法用于处理集合的合并和查询问题，它定义了两个用于并查集的操作：
- \(find\) ：确定元素属于哪一个子集，或判断两个元素是否属于同一子集；
- \(union\) ：将两个子集合并为一个子集。
思路
使用一维数组来记录每一个节点的父节点，如果它是根节点，就指向自己。
代码实现
class UnionFind(object):
def __int__(self, n: int):
self._count = n
self._parent = [i for i in range(n)]
# 记录每棵树的重量
self._size = [1] * n
def union(self, p: int, q: int):
""" 连接两个节点 """
root_p = self.find(p)
root_q = self.find(q)
if root_p == root_q:
return
# 将小树接到大树下面：保证树平衡
if self._size[root_p] > self._size[root_q]:
self._parent[root_q] = root_p
self._size[root_p] += self._size[root_q]
else:
self._parent[root_p] = root_q
self._size[root_q] += self._size[root_p]
self._count -= 1
return
def connected(self, p: int, q: int):
return self.find(p) == self.find(q)
def find(self, x: int):
""" 返回某个节点的根节点 """
while self._parent[x] != x:
# 压缩路径：使当前节点的父节点指向父节点的父节点
self._parent[x] = self._parent[self._parent[x]]
x = self._parent[x]
return x
def get_count(self):
return self._count
应用
应用1：Leetcode.130
题目
分析
为了使用并查集算法，我们需要将 \(n * m\) 的二维数组转换为以为一维数组，以二维坐标 \((x,\ y)\) 为例：
\[(x,\ y) \Rightarrow x * n + y \]这是将二维坐标映射到一维坐标常用的技巧。
首先，将边界四周为 "O" 的元素的父节点指向一个虚拟节点 \(dummy\) ，由于初始化并查集数组最多会用到 \(m * n - 1\) ， 所以，这里我们假设:
\[dummy = n * m \]然后，再遍历内部元素，如果当前元素为 "O"，则将该元素与其四周为 "O" 的元素连通。
最后，再遍历一次所有元素，将没有与 \(dummy\) 节点连通元素置为 "X" 即可。
代码实现
from typing import List
class UnionFind(object):
def __init__(self, n: int):
self._count = n
self._parent = [i for i in range(n)]
# 记录每棵树的重量
self._size = [1] * n
def union(self, p: int, q: int):
""" 连接两个节点 """
root_p = self.find(p)
root_q = self.find(q)
if root_p == root_q:
return
# 将小树接到大树下面：保证树平衡
if self._size[root_p] > self._size[root_q]:
self._parent[root_q] = root_p
self._size[root_p] += self._size[root_q]
else:
self._parent[root_p] = root_q
self._size[root_q] += self._size[root_p]
self._count -= 1
return
def connected(self, p: int, q: int):
return self.find(p) == self.find(q)
def find(self, x: int):
""" 返回某个节点的根节点 """
while self._parent[x] != x:
# 压缩路径：使当前节点的父节点指向父节点的父节点
self._parent[x] = self._parent[self._parent[x]]
x = self._parent[x]
return x
def get_count(self):
return self._count
DIRECTIONS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if len(board) == 0:
return
m, n = len(board), len(board[0])
uf = UnionFind(m * n + 1)
dummy = m * n
# 遍历第一列和最后一列元素，将为O的元素与dummy相连
for i in range(m):
if board[i][0] == "O":
uf.union(i * n, dummy)
if board[i][n - 1] == "O":
uf.union(i * n + n - 1, dummy)
# 遍历第一行和最后一行元素，将为O的元素与dummy相连
for j in range(n):
if board[0][j] == "O":
uf.union(j, dummy)
if board[m - 1][j] == "O":
uf.union((m - 1) * n + j, dummy)
# 将与边界相连的"O"连通
for i in range(1, m - 1):
for j in range(1, n - 1):
# 如果当前元素是O
if board[i][j] == "O":
# 将它四周是O的元素连通
for direction in DIRECTIONS:
x, y = direction[0] + i, direction[1] + j
if board[x][y] == "O":
uf.union(x * n + y, i * n + j)
for i in range(m):
for j in range(n):
# 如果它和dummy不是连通的，就置为X
if not uf.connected(i * n + j, dummy):
board[i][j] = "X"
return board