并查集

并查集（Disjoint Set Union，DSU）用于维护若干个互不相交的集合。它主要支持两类操作：

  • 查询：判断两个元素是否属于同一个集合；
  • 合并：把两个元素所在的集合合并成一个集合。

例如，在维护无向图的连通性时，可以把同一个连通块中的所有点看作一个集合。每加入一条连接两个点的边，就合并这两个点所在的集合；查询两个点是否连通，就判断它们是否属于同一个集合。

并查集不能直接删除集合中的元素，也不能高效维护集合内部的顺序。它适合处理只需要不断合并、查询连通关系的问题。

树形表示

并查集把每个集合表示成一棵树，并用数组 p 保存每个节点的父节点：

int p[N];

如果 p[x] == x，说明 x 没有更上层的父节点，是当前集合的根节点，也称为代表元。属于同一个集合的所有元素最终都会沿父节点指针到达同一个根节点。

因此，判断 a 和 b 是否属于同一个集合，只需比较它们的根节点：

find(a) == find(b)

初始化

最初每个元素各自组成一个集合，所以每个节点都是自己的根节点。若还要维护集合大小，则每个集合初始只有一个元素：

for (int i = 1; i <= n; i++) {
  p[i] = i;
  sz[i] = 1;
}

查找根节点与路径压缩

如果 p[x] != x，说明 x 不是根节点，需要继续向上查找。最直接的递归写法是：

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

其中，下面这条赋值语句实现了路径压缩：

p[x] = find(p[x]);

递归返回根节点后，沿途节点的父节点都会被直接修改为根节点。以后再次查询这些节点时，不必再逐层向上查找。

例如，原来的父节点关系为 1 -> 2 -> 3 -> 4，并且 4 是根节点。执行 find(1) 后，1、2、3 都会直接指向 4。路径压缩不会改变集合包含哪些元素，只会缩短树的高度。

合并两个集合

设 a 和 b 的根节点分别为 ra 和 rb：

int ra = find(a);
int rb = find(b);

如果 ra == rb，说明两个元素已经属于同一个集合，不需要再次合并。否则，只需让其中一个根节点指向另一个根节点：

p[ra] = rb;

合并方向不会影响集合划分的正确性。为了让树尽量矮，可以使用按集合大小合并：总是把较小集合的根节点连接到较大集合的根节点。

if (sz[ra] > sz[rb]) {
  swap(ra, rb);
}
 
sz[rb] += sz[ra];
p[ra] = rb;

这里交换后保证 sz[ra] <= sz[rb]，因此把 ra 所在的较小集合合并到 rb 所在的较大集合。

为什么集合大小只记录在根节点上

数组 sz[root] 表示以 root 为根的集合所包含的元素数量。只有根节点处的大小有效，普通节点的旧值不需要更新，因为查询时总是先找到根节点：

int count = sz[find(x)];

合并两个不同集合时，新集合的大小等于两个原集合大小之和：

sz[rb] += sz[ra];

如果不先判断 ra == rb，重复合并同一个集合会把集合大小错误地累加两次。

为什么原写法要先计算大小

如果不缓存根节点，而是重复调用 find：

sz[find(b)] += sz[find(a)];
p[find(a)] = find(b);

就必须先更新大小，再修改父节点。因为一旦先让 a 的根节点指向 b 的根节点，之后的 find(a) 和 find(b) 会返回同一个根节点，再相加就会得到错误结果。

更推荐先把两个根节点分别保存到 ra、rb 中。这样可以避免重复查找，也能让“比较根节点、更新大小、连接根节点”的合并过程更清楚。

可复用数组模板

下面的模板同时使用路径压缩和按集合大小合并，并提供初始化、合并、连通性查询和集合大小查询：

#include <utility>
 
using namespace std;
 
const int N = 100010;
 
int p[N], sz[N];
 
int find(int x) {
  if (p[x] != x) {
    p[x] = find(p[x]);
  }
  return p[x];
}
 
void init(int n) {
  for (int i = 1; i <= n; i++) {
    p[i] = i;
    sz[i] = 1;
  }
}
 
void merge(int a, int b) {
  int ra = find(a);
  int rb = find(b);
 
  if (ra == rb) {
    return;
  }
 
  if (sz[ra] > sz[rb]) {
    swap(ra, rb);
  }
 
  sz[rb] += sz[ra];
  p[ra] = rb;
}
 
bool same(int a, int b) {
  return find(a) == find(b);
}
 
int componentSize(int x) {
  return sz[find(x)];
}

正确性说明

初始化后，每个元素都是一棵只包含自身的树，所以此时的集合划分正确，且每个根节点记录的集合大小都为 1。

执行 find(x) 时，递归会沿父节点指针到达唯一满足 p[root] == root 的节点，并返回该根节点。路径压缩只是让搜索路径上的节点直接指向同一个根节点，不会把节点移动到其他集合，因此不会改变集合划分。

合并时，如果 find(a) == find(b)，两个元素原本就在同一个集合中，保持现状即可。如果根节点不同，让一个根节点指向另一个根节点后，两棵树会连接成一棵树，原来两个集合中的所有节点将拥有同一个根节点，而其他集合不受影响。新根节点记录的大小又被更新为两个原集合大小之和，因此集合大小也保持正确。

由此可知，任意次操作后，两个元素属于同一个集合，当且仅当它们的根节点相同；sz[find(x)] 也始终等于 x 所在集合的元素数量。

AcWing 837：连通块中点的数量

题意

给定 n 个点，初始时每个点各自位于一个连通块中。接下来执行 m 个操作：

  • C a b：在点 a 和点 b 之间连一条边；如果它们不在同一个连通块中，就合并两个连通块；
  • Q1 a b：询问点 a 和点 b 是否在同一个连通块中；
  • Q2 a：询问点 a 所在连通块包含多少个点。

对于 Q1 操作，如果两个点连通，输出 Yes，否则输出 No。

解题思路

把每个连通块看作一个集合，并用并查集维护：

  1. 初始化时令 p[i] = i、sz[i] = 1；
  2. 遇到 C a b 时，找到两个点的根节点。如果根节点不同，就合并两个集合，并累加集合大小；
  3. 遇到 Q1 a b 时，比较 find(a) 和 find(b) 是否相等；
  4. 遇到 Q2 a 时，输出 sz[find(a)]。

完整代码

#include <iostream>
#include <string>
#include <utility>
 
using namespace std;
 
const int N = 100010;
 
int p[N], sz[N];
 
int find(int x) {
  if (p[x] != x) {
    p[x] = find(p[x]);
  }
  return p[x];
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int n, m;
  cin >> n >> m;
 
  for (int i = 1; i <= n; i++) {
    p[i] = i;
    sz[i] = 1;
  }
 
  while (m--) {
    string op;
    cin >> op;
 
    if (op == "C") {
      int a, b;
      cin >> a >> b;
 
      int ra = find(a);
      int rb = find(b);
 
      if (ra == rb) {
        continue;
      }
 
      // 按集合大小合并：把较小集合连接到较大集合。
      if (sz[ra] > sz[rb]) {
        swap(ra, rb);
      }
 
      sz[rb] += sz[ra];
      p[ra] = rb;
    } else if (op == "Q1") {
      int a, b;
      cin >> a >> b;
      cout << (find(a) == find(b) ? "Yes" : "No") << '\n';
    } else {
      int a;
      cin >> a;
      cout << sz[find(a)] << '\n';
    }
  }
 
  return 0;
}

样例推演

假设有 5 个点，依次执行：

C 1 2
C 2 5
Q1 1 5
Q2 2
Q1 1 3

前两次操作把 1、2、5 合并到同一个集合中。因此：

  • Q1 1 5 输出 Yes；
  • Q2 2 输出 3；
  • 点 3 仍在单独的集合中，所以 Q1 1 3 输出 No。

复杂度分析

同时使用路径压缩和按集合大小合并后，单次查找或合并的均摊时间复杂度为 O(α(n))O(\alpha(n))，其中 α\alpha 是反阿克曼函数，在实际数据范围内可以视为一个极小的常数。

因此：

  • 初始化的时间复杂度为 O(n)O(n)；
  • 执行 m 次操作的总时间复杂度为 O(n+mα(n))O(n + m\alpha(n))；
  • p 数组和 sz 数组的空间复杂度为 O(n)O(n)。

常见错误

  • 忘记初始化父节点：必须令 p[i] = i，否则无法判断一个节点是否为根节点。
  • 路径压缩漏掉赋值：只写 find(p[x]) 不会压缩路径，应写成 p[x] = find(p[x])。
  • 同一集合被重复累加：合并前必须判断两个根节点是否相同，否则会把集合大小重复计算。
  • 在普通节点上查询大小：只有根节点处的 sz 有效，应使用 sz[find(x)]，不能直接使用 sz[x]。
  • 修改父节点后才重新查大小：若重复调用 find，先连接根节点会改变后续 find(a) 的结果。最好先缓存 ra 和 rb。
  • 忘记更新集合大小：只修改 p[ra] 会正确维护连通性，但 Q2 的结果会错误。
  • 合并大小加反：让 p[ra] = rb 时，应把 sz[ra] 加到 sz[rb] 上；如果合并方向相反，更新方向也要相反。
  • 输出大小写不符合要求：本题要求输出 Yes 和 No，不是全大写的 YES 和 NO。
  • 把 Q2 当成双参数操作：Q2 后面只有一个点编号，读取多余参数会导致后续输入错位。

参考资料