21-算法与数据结构
第 290 题:并查集(Union-Find)的实现?path compression?
题目
并查集(Union-Find)的实现?path compression?
完整讲解
一、并查集用途
维护** disjoint sets**(无交集合),支持 Union(合并两集合)与 Find(查某元素所属集合代表元),用于判连通、等价类、最小生成树(Kruskal)等。目标:Union 与 Find 尽量快,均摊近 O(1)。
二、基本实现
用父指针数组 parent[]:parent[i] 为 i 的父节点,根节点 parent[i]=i 或 -1。Find(x):沿 parent 一路向上直到根,返回根。Union(x,y):Find 得到 x、y 的根 rx、ry,将 rx 的 parent 设为 ry(或按秩挂)。朴素实现 Find/Union 最坏 O(n);路径压缩与按秩合并可均摊到近 O(1)。
三、Path compression(路径压缩)
Find 时,把从 x 到根路径上所有节点的 parent 直接改为根。这样下次 Find 这些节点为 O(1)。实现:递归 Find 中在返回前写 parent[x]=Find(parent[x]);或迭代两次,第一次找根、第二次把路径全部挂到根。与按秩合并(小树挂到大树根下)一起,均摊复杂度 O(α(n)),α 为反阿克曼函数,实际可视为常数。
面试要点
- 并查集:维护不相交集合;Union 合并、Find 查代表元。
- 实现:parent 数组;Find 沿 parent 找根;Union 把两集合的根挂一起。
- 路径压缩:Find 时把路径上节点直接连到根,下次 Find 更快。
- 按秩合并:小树挂大树下;与路径压缩一起均摊近 O(1)。
记忆要点
- parent 数组;Find 找根、Union 并根。
- 路径压缩 = Find 时把路径挂到根。
- 按秩合并 + 路径压缩 → 均摊 O(α(n))。