如果节点 p 和 q 连通的话，一定拥有相同的根节点
class UF {
// 记录连通分量
private int count;
// 节点 x 的父节点是 parent[x]
private int[] parent;
/* 构造函数，n 为图的节点总数 */
public UF(int n) {
// 一开始互不连通
this.count = n;
// 父节点指针初始指向自己
parent = new int[n];
for (int i = 0; i < n; i++)
parent[i] = i;
}
/* 其他函数 */
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
// 将两棵树合并为一棵
parent[rootP] = rootQ;
// parent[rootQ] = rootP 也一样
count--; // 两个分量合二为一
}
/* 返回某个节点 x 的根节点 */
private int find(int x) {
// 根节点的 parent[x] == x
while (parent[x] != x)
x = parent[x];
return x;
}
/* 返回当前的连通分量个数 */
public int count() {
return count;
}
public boolean connected(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}
复杂度：O(n）
平衡性优化, 复杂度：O(log n)
class UF {
private int count;
private int[] parent;
// 新增一个数组记录树的“重量”
private int[] size;
public UF(int n) {
this.count = n;
parent = new int[n];
// 最初每棵树只有一个节点
// 重量应该初始化 1
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
/* 其他函数 */
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
// 小树接到大树下面，较平衡
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
} else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
count--;
}
路径压缩
进一步压缩每棵树的高度，使树高始终保持为常数
// 第一种路径压缩的 find 方法
private int find(int x) {
while (parent[x] != x) {
// 这行代码进行路径压缩
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
// 第二种路径压缩的 find 方法
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
class UF {
// 连通分量个数
private int count;
// 存储每个节点的父节点
private int[] parent;
// n 为图中节点的个数
public UF(int n) {
this.count = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// 将节点 p 和节点 q 连通
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
parent[rootQ] = rootP;
// 两个连通分量合并成一个连通分量
count--;
}
// 判断节点 p 和节点 q 是否连通
public boolean connected(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// 返回图中的连通分量个数
public int count() {
return count;
}
}
Union-Find 算法的复杂度可以这样分析：构造函数初始化数据结构需要 O(N) 的时间和空间复杂度；连通两个节点 union、判断两个节点的连通性 connected、计算连通分量 count 所需的时间复杂度均为 O(1)。
323. Number of Connected Components in an Undirected Graph
- 思路
- example
- DFS
- 复杂度. 时间：O(?), 空间: O(?)
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
def dfs(graph, i):
visited[i] = True
for j in graph[i]:
if not visited[j]:
dfs(graph, j)
# 建立无向图（邻接表）
graph = collections.defaultdict(list)
for edge in edges:
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
cnt = 0
visited = [False for _ in range(n)]
for i in range(n):
if not visited[i]:
dfs(graph, i)
cnt += 1
return cnt
- 并查集
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
class UF:
def __init__(self, n):
self.count = n
self.parent = [i for i in range(n)]
def find(self, p):
if p != self.parent[p]:
self.parent[p] = self.find(self.parent[p])
return self.parent[p]
def union(self, p, q):
if self.find(p) == self.find(q):
return
# self.parent[self.parent[p]] = self.parent[q] # wrong
self.parent[self.find(p)] = self.find(q)
self.count -= 1
uf = UF(n)
for edge in edges:
uf.union(edge[0], edge[1])
return uf.count
130. Surrounded Regions
- 思路
- example
- DFS (更自然）
先用 for 循环遍历棋盘的四边，用 DFS 算法把那些与边界相连的 O 换成一个特殊字符，比如 #；然后再遍历整个棋盘，把剩下的 O 换成 X，把 # 恢复成 O。
- 复杂度. 时间：O(?), 空间: O(?)
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def dfs(board, i, j, replacement):
if i < 0 or i >= m or j < 0 or j >= n:
return
if board[i][j] != 'O':
return
board[i][j] = replacement
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for direction in directions:
dx, dy = direction[0], direction[1]
x, y = i + dx, j + dy
dfs(board, x, y, replacement)
m, n = len(board), len(board[0])
# 边界
for j in range(n):
if board[0][j] == 'O':
dfs(board, 0, j, '#')
if board[m-1][j] == 'O':
dfs(board, m-1, j, '#')
for i in range(m):
if board[i][0] == 'O':
dfs(board, i, 0, '#')
if board[i][n-1] == 'O':
dfs(board, i, n-1, '#')
# 内部以及边界
for i in range(m):
for j in range(n):
if board[i][j] == 'O':
board[i][j] = 'X'
if board[i][j] == '#':
board[i][j] = 'O'
-
并查集
code
990. Satisfiability of Equality Equations
- 思路
- example
- 类似于检查冲突
动态连通性其实就是一种等价关系
核心思想是，将 equations 中的算式根据 == 和 != 分成两部分，先处理 == 算式，使得他们通过相等关系各自勾结成门派（连通分量）；然后处理 != 算式，检查不等关系是否破坏了相等关系的连通性。
- 复杂度. 时间：O(?), 空间: O(?)
class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
class UF:
def __init__(self, n):
self.count = n
self.parent = [i for i in range(n)]
def find(self, p):
if p != self.parent[p]:
self.parent[p] = self.find(self.parent[p])
return self.parent[p]
def union(self, p, q):
rootP = self.find(p)
rootQ = self.find(q)
if rootP == rootQ:
return
self.parent[rootP] = rootQ
self.count -= 1
def connected(self, p, q):
return self.find(p) == self.find(q)
uf = UF(26) # 26 letters
# 连通分类
for equation in equations:
if equation[1] == '=':
p, q = equation[0], equation[3]
uf.union(ord(p) - ord('a'), ord(q) - ord('a'))
# 检查连通性
for equation in equations:
if equation[1] == '!':
p, q = equation[0], equation[3]
if uf.connected(ord(p)-ord('a'), ord(q)-ord('a')):
return False
return True
