并查集实现

路径压缩 + 按大小合并的并查集实现,含调用示例和实现细节。

时间 O(alpha(n)) 均摊,空间 O(n) · 标签 数据结构 / 并查集 / 实现

本页只放实现;概念与优化见 并查集 和 并查集优化。

使用约定

  • 元素用 0-index 编号;1-index 时构造 DSU dsu(n + 1)。
  • find(x) 返回代表元。
  • unite(a, b) 返回是否真的发生了合并;已经在同一集合时返回 false。
  • size(x) 返回 𝑥 所在集合的大小。

实现

struct DSU {
  vector<int> fa, sz;

  explicit DSU(int n) : fa(n), sz(n, 1) {
    iota(fa.begin(), fa.end(), 0);
  }

  int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
  }

  bool unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return false;
    if (sz[a] < sz[b]) swap(a, b);
    fa[b] = a;
    sz[a] += sz[b];
    return true;
  }

  int size(int x) {
    return sz[find(x)];
  }
};

调用示例

统计无向图的连通分量数量:

DSU dsu(n);
int components = n;

for (auto [u, v] : edges) {
  if (dsu.unite(u, v)) --components;
}

cout << components << '\n';

实现细节

  • fa 初始化成自身;sz 初始化成 1。
  • find 使用路径压缩:fa[x] = find(fa[x])。
  • 合并时按大小把较小的树挂到较大的树下。
  • sz 只在根节点有意义,size(x) 要先 find(x)。
  • 自环或重复边调用 unite 会返回 false,不会改变任何集合。
  • 递归 find 在极端情况下可能很深;路径压缩后一般没问题,必要时改迭代。
  • 标准并查集不支持删除;需要回滚时用可撤销并查集。

复杂度

操作均摊复杂度说明
find𝑂(𝛼(𝑛))路径压缩
unite𝑂(𝛼(𝑛))两次 find + 按大小合并
空间𝑂(𝑛)fa 与 sz

其中 𝛼(𝑛) 是反阿克曼函数,实际可视为常数。

对应例题

  • 洛谷 P3367:【模板】并查集
  • 洛谷 P1551:亲戚
  • 洛谷 P3958:奶酪(连通性判断)
  • 洛谷 P2024:[NOI2001] 食物链(扩展域 / 带权并查集)
  • 洛谷 P1197:[JSOI2008] 星球大战(逆向加边)
源码位置