LeetCode 并查集应用总结题解

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) 的操作复杂度。