IT 面试题库

并查集的路径压缩和按秩合并为什么能把复杂度降到接近 O(1)?如何用它判断连通分量和环?

中级编程题算法工程师后端开发工程师并查集路径压缩按秩合并连通分量

题目

考察并查集的两个优化、均摊复杂度和图论中的典型应用。

参考答案

内容深度:详细 · 含示例/代码 · 来源:外部链接 · 未复核 · 29 天前更新

基本操作

两个优化

判断连通分量

判断环(无向图)

代码骨架

parent = list(range(n))
rank = [0] * n
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x
def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb: return False
    if rank[ra] < rank[rb]: ra, rb = rb, ra
    parent[rb] = ra
    if rank[ra] == rank[rb]: rank[ra] += 1
    return True

应用

坑

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题