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 操作时将路径上的所有节点指向根节点。