并查集实现:路径压缩与按秩合并
哪些公司问过
答案要点
- 初始化:parent[i]=i,size 初始化为 1 或 rank 初始化为 0
- find 路径压缩:把路径上节点直接指向根,或迭代路径减半
- union 按秩/按大小合并:小树根挂到大树根下,并更新 size/rank
- 两者结合后均摊复杂度 O(α(n)),近似常数
- 可维护连通分量数;数据量大时用迭代 find 防栈溢出
易错点
- 合并时直接 parent[x]=y,而不是连接两者的根
- 按 rank 合并时,两树等高也忘了将新根的 rank 加 1
- 以为并查集支持高效的拆分操作
面试官常见追问
- 只用路径压缩不按秩合并会怎样?
- 并查集常用在哪些题?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。