跳到主要内容

并查集的定义与操作

并查集解决什么问题？​

  • 并查集 (Union-Find): 维护一组不相交集合的数据结构, 支持动态合并集合与查询归属;
  • 典型用途: 判断两元素是否同属一个集合、统计连通块数量、Kruskal 最小生成树;
  • 内部结构: 用树或森林表示集合, 每棵树的根节点代表整个集合;

并查集提供哪些操作？​

操作含义
find(x)返回 x 所在集合的代表 (根节点)
union(x, y)合并 x 与 y 所在的两个集合
isConnected(x, y)判断两者是否同集合, 即 find(x) === find(y)
  • 幂等: 两个元素本已同属一个集合时, union 不做任何事;
  • 复杂度来源: 所有优化都在缩短 find 的路径长度;

用数组如何存储森林？​

  • fa[x]: 元素 x 的父节点下标;
  • 初始化: fa[x] = x, 每个元素自成一个集合;
  • 根节点: 满足 fa[x] === x 的节点;
  • 查找: 沿父指针不断上溯到根节点;
const fa = Array.from({ length: n }, (_, i) => i);
let root = x;
while (fa[root] !== root) root = fa[root];