C++怎么实现一个并查集_C++数据结构中Disjoint Set Union的路径压缩与按秩合并

并查集通过路径压缩和按秩合并优化，显著提升操作效率。1. 初始化每个元素父节点为自身，秩为0；2. 查找时递归压缩路径，使节点直连根；3. 合并时按秩挂载，小秩并入大秩，相等则任选根并增秩。此结构支持高效集合查询与合并，平均时间接近常数。

在C++中实现并查集（Disjoint Set Union, DSU）时，路径压缩和按秩合并是两个关键优化技术，它们能显著提升查找与合并操作的效率，使平均时间复杂度接近常数级别。

基本结构设计

并查集用于维护一组元素的划分，支持快速查找某个元素所属集合以及合并两个集合。核心是用数组存储每个节点的父节点。

初始化时，每个元素的父节点指向自己，表示独立集合。可以用一个vector保存parent信息，另一个记录每个集合的秩（rank），用于按秩合并。

vector parent; // 父节点索引 vector rank; // 树的高度上界

路径压缩（Path Compression）

在查找根节点的过程中，把沿途的所有节点直接连接到根，从而压平树结构。这样后续查找会更快。

立即学习“C++免费学习笔记（深入）”；

查找函数使用递归实现路径压缩非常简洁：

• 如果当前节点不是根（parent[x] != x），则递归查找根，并将parent[x]更新为返回值
• 最终返回根节点

这一操作让整条路径上的节点都指向根，极大减少未来查找深度。

豆绘AI

豆绘AI是国内领先的AI绘图与设计平台，支持照片、设计、绘画的一键生成。

485

查看详情

int find(int x) {
  if (parent[x] != x)
    parent[x] = find(parent[x]);
  return parent[x];
}

按秩合并（Union by Rank）

合并两个集合时，通过比较两棵树的秩决定挂载方向：将秩较小的树根连到秩较大的树根下。若秩相等，则任选一方作为新根，并将其秩加一。

这样做可以避免生成过深的树，控制整体高度。

• 找到两个元素的根
• 比较对应秩的大小
• 小秩向大秩合并
• 相同秩时更新新根的秩

void unite(int x, int y) {
  int rx = find(x), ry = find(y);
  if (rx == ry) return;
  if (rank[rx]     parent[rx] = ry;
  else if (rank[rx] > rank[ry])
    parent[ry] = rx;
  else {
    parent[ry] = rx;
    ++rank[rx];
  }
}

完整实现示例

封装成类更便于管理。构造函数初始化每个节点为独立集合。

假设处理n个编号从0到n-1的元素：

struct DSU {
  vector parent, rank;
  DSU(int n) {
    parent.resize(n);
    rank.resize(n, 0);
    for (int i = 0; i   }
  int find(int x) { ... }
  void unite(int x, int y) { ... }
};

这个结构可在Kruskal算法、连通分量判断等场景中高效使用。

基本上就这些。路径压缩配合按秩合并，使得DSU的操作几乎是常数时间，适合大规模数据处理。注意两者结合效果最佳，单独使用任一优化也能带来明显提升。

以上就是C++怎么实现一个并查集_C++数据结构中Disjoint Set Union的路径压缩与按秩合并的详细内容，更多请关注php中文网其它相关文章！