跳到主要内容

并查集

并查集（Union-find set）是一种树形的数据结构，顾名思义，它用于处理一些不交集的 合并 及 查询 问题。 它支持两种操作：

  • 查找（Find）：确定某个元素处于哪个子集
  • 合并（Union）：将两个子集合并成一个集合

其优点是在足够多的合并和查询操作后，均摊下来单次的查询时间复杂度是O(1)， 常见于图的连通性问题中。

查找​

朴素实现​

vector<int> parent;  // 记录某个人的爸爸是谁，特别规定，祖先的爸爸是他自己

// 递归
int find(int x) {
  // 寻找x的祖先
  if (parent[x] == x) {  // 如果 x 是祖先则返回
    return x;
  } else {
    return find(parent[x]);  // 如果不是则 x 的爸爸问 x 的爷爷
  }
}

// 非递归
int find(int x) {
  while (x != parent[x]) {  // 如果 x 不是祖先，就一直往上一辈找
    x = parent[x];
  }
  return x;  // 如果 x 是祖先则返回
}

路径压缩​

这样的确可以达成目的，但是显然效率实在太低。为什么呢？因为我们使用了太多没用的信息，我的祖先是谁与我父亲是谁没什么关系，这样一层一层找太浪费时间，不如我直接当祖先的儿子，问一次就可以出结果了。甚至祖先是谁都无所谓，只要这个人可以代表我们家族就能得到想要的效果。把在路径上的每个节点都直接连接到根上，这就是路径压缩。

// 递归
int find(int x) {
  if (x != parent[x]) {  // x 不是自身的父亲，即 x 不是该集合的代表
    parent[x] = find(parent[x]);  // 查找 x 的祖先直到找到代表，于是顺手路径压缩
  }
  return parent[x];
}

// 非递归
int find(int x) {
  int p = x, t;
  while (p != parent[p]) {  // 如果 p 不是祖先，就一直往上一辈找, 找到祖先为止
    p = parent[p];
  }

  while (x != p) {  // 沿路更新所有节点的祖先
    t = parent[x];
    parent[x] = p;
    x = t;
  }
  return p;
}

合并​

朴素实现​

void merge(int x, int y) {
  // x 与 y 所在的树合并
  x = find(x);
  y = find(y);
  parent[x] = y;  // 把 x 的祖先变成 y 的祖先的儿子
}

按秩合并​

由于需要我们支持的只有集合的合并、查询操作，当我们需要将两个集合合二为一时，无论将哪一个集合连接到另一个集合的下面，都能得到正确的结果。但不同的连接方法存在时间复杂度的差异。具体来说，如果我们将一棵点数与深度都较小的集合树连接到一棵更大的集合树下，显然相比于另一种连接方案，接下来执行查找操作的用时更小（也会带来更优的最坏时间复杂度）。

通常为了方便实现， 我们选择以点数作为秩函数

如果是大树挂到小树上的话， 在使用路径压缩的情况下， 下一次 find 的时候则需要更新更多的节点

vector<int> rank(N, 1);  // 记录并初始化子树的大小为 1

void merge(int x, int y) {
  x = find(x), y = find(y);
  if (x == y) {
    return;
  } else if (rank[x] > rank[y]) {  // 保证小的合到大的里
    swap(x, y);
  }
  parent[x] = y;
  rank[y] += rank[x];
}

复杂度​

时间复杂度​

同时使用路径压缩和启发式合并之后，并查集的每个操作平均时间仅为O(α(n))O(\alpha(n)) ，其中α\alpha为阿克曼函数的反函数，其增长极其缓慢，也就是说其单次操作的平均运行时间可以认为是一个很小的常数。

信息

Ackermann 函数 A(m,n)A(m, n) 的定义是这样的:

A(m,n)={n+1 if m=0A(m−1,1) if m>0 and n=0A(m−1,A(m,n−1)) otherwise A(m, n)= \begin{cases}n+1 & \text { if } m=0 \\ A(m-1,1) & \text { if } m>0 \text { and } n=0 \\ A(m-1, A(m, n-1)) & \text { otherwise }\end{cases}

而反 Ackermann 函数 α(n)\alpha(n) 的定义是阿克曼函数的反函数, 即为最大的整数 mm 使得 A(m,m)⩽nA(m,m) \leqslant n

时间复杂度的证明请参考这个页面。

空间复杂度​

显然为 O(n)O(n)