LeetCode 路径压缩优化题解

LeetCode 路径压缩优化题解题目描述解释并实现带路径压缩的并查集。解题思路方法路径压缩思路在 find 操作时将路径上的所有节点的父节点直接指向根节点。这样可以加速后续的查询操作。复杂度分析时间复杂度O(α(n))α 是反阿克曼函数。空间复杂度O(n)。代码实现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 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 # 测试 def test_union_find(): uf UnionFind(5) uf.union(0, 1) uf.union(1, 2) uf.union(3, 4) print(uf.find(2)) # 输出0 print(uf.find(4)) # 输出3 if __name__ __main__: test_union_find()总结路径压缩是并查集的重要优化在 find 操作时将路径上的所有节点指向根节点。