企业官网建设流程全解析

LeetCode 并查集应用总结题解

题目描述

总结并查集的各种应用场景。

并查集的应用场景

1. 朋友圈

• 将所有朋友关系合并到同一个集合。
• 最后统计集合数量。

2. 岛屿数量

• 将相邻的陆地合并到同一个集合。
• 最后统计集合数量。

3. 冗余连接

• 如果两个节点已经在同一个集合中，则这条边是冗余的。
• 找出构成环的边。

4. 最小生成树

• 使用 Kruskal 算法，按权重排序边，合并不在同一集合的节点。

5. 相似字符串组

• 将相似的字符串合并到同一个集合。
• 最后统计集合数量。

代码实现

class UnionFind: def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): px, py = self.find(x), self.find(y) if px == py: return False if self.rank[px] < self.rank[py]: px, py = py, px self.parent[py] = px if self.rank[px] == self.rank[py]: self.rank[px] += 1 return True def connected(self, x, y): return self.find(x) == self.find(y) # 测试 def test_union_find(): uf = UnionFind(5) uf.union(0, 1) uf.union(1, 2) print(uf.connected(0, 2)) # 输出：True print(uf.connected(0, 3)) # 输出：False if __name__ == "__main__": test_union_find()

总结

并查集是一种高效的数据结构，适用于处理集合合并和查询问题。通过路径压缩和按秩合并优化，可以实现近乎 O(1) 的操作复杂度。