引入

给定 n 个元素和若干组关系，每组关系表示两个元素属于同一集合。需要支持以下操作：

  1. 合并：将两个元素所在的集合合并为一个集合。
  2. 查询：判断两个元素是否在同一集合中。

这就是经典的并查集（Disjoint Set Union，DSU）问题。

例题：洛谷 P3367 【模板】并查集。

基本实现

核心思想

用一棵有根树表示一个集合，树的根节点作为该集合的代表元素。

用 fa[x] 记录节点 x 的父节点。初始时，每个元素独立成一个集合，即 fa[x] = x。

查找

查找元素 x 所在集合的代表元素（即树的根）：

1
2
3
4
int find(int x) {
  while (fa[x] != x) x = fa[x];
  return x;
}

合并

将 x 和 y 所在的集合合并，只需让一棵树的根指向另一棵树的根：

1
2
3
void merge(int x, int y) {
  fa[find(x)] = find(y);
}

查询

1
2
3
bool query(int x, int y) {
  return find(x) == find(y);
}

但这样的实现有一个问题：树可能退化成链，导致 find 的时间复杂度退化为 O(n)。

路径压缩

在 find 的过程中，我们将路径上所有节点直接指向根节点，这样下次查询时就是 O(1) 的。

1
2
3
4
int find(int x) {
  if (fa[x] != x) fa[x] = find(fa[x]);
  return fa[x];
}

仅使用路径压缩的并查集，find 的均摊时间复杂度为 O(log n)。

按秩合并

另一个优化是按秩合并（Union by Rank）：合并时，将秩较小的树接到秩较大的树上，以减小树的高度。

这里的”秩”可以是树的高度（启发式合并），也可以是集合的大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int fa[N], rnk[N];

void init(int n) {
  for (int i = 1; i <= n; ++i)
    fa[i] = i, rnk[i] = 1;
}

void merge(int x, int y) {
  x = find(x), y = find(y);
  if (x == y) return;
  if (rnk[x] > rnk[y]) std::swap(x, y);
  fa[x] = y;
  if (rnk[x] == rnk[y]) ++rnk[y];
}

仅使用按秩合并的并查集，find 的时间复杂度为 O(log n)。

同时使用两种优化

当路径压缩和按秩合并同时使用时，find 和 merge 的均摊时间复杂度为 O(α(n))，其中 α 是阿克曼函数的反函数，增长极其缓慢。对于实际中的 n（n ≤ 1018），α(n) ≤ 4。

因此可以认为并查集的每次操作几乎是 O(1) 的。

不过实际竞赛中，只用路径压缩就已经足够快了，代码也更简洁。按秩合并更多用于需要可撤销并查集的场景（路径压缩不可撤销）。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

const int N = 1e4 + 10;
int n, m, fa[N];

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

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++i) fa[i] = i;
  for (int op, x, y; m; --m) {
    std::cin >> op >> x >> y;
    if (op == 1) fa[find(x)] = find(y);
    else std::cout << (find(x) == find(y) ? "Y" : "N") << '\n';
  }
  std::cout.flush();
  return 0;
}

带权并查集

有时候我们不仅需要知道两个元素是否在同一集合，还需要维护它们之间的某种关系或权值。

例题：食物链

例题：洛谷 P2024 [NOI2001] 食物链。

题意简述

有三类动物 A, B, C，A 吃 B，B 吃 C，C 吃 A。给定 n 个动物和 k 条信息，每条信息为”x 和 y 同类”或”x 吃 y“。求有多少条信息是假话。

算法分析

使用带权并查集，用 dx 表示 x 到其所在集合根节点的”距离”，对 3 取模后：

  • dx mod  3 = 0：x 与根同类。
  • dx mod  3 = 1：x 吃根。
  • dx mod  3 = 2：根吃 x。

路径压缩时需要同步更新权值：

1
2
3
4
5
6
7
8
int find(int x) {
  if (fa[x] != x) {
    int root = find(fa[x]);
    d[x] += d[fa[x]];
    fa[x] = root;
  }
  return fa[x];
}

合并时，根据两个元素的关系和各自到根的距离，计算新的边权。

具体实现可以参考洛谷题解，此处不再展开。

扩展域并查集

另一种处理关系的方法是扩展域并查集：将每个元素拆成 k 个”分身”，放在不同的”域”中。

以食物链为例，将每个动物 x 拆为 xA, xB, xC（分别对应 x 是 A/B/C 类）。

  • “x 和 y 同类”：合并 (xA, yA), (xB, yB), (xC, yC)。
  • “x 吃 y”：合并 (xA, yB), (xB, yC), (xC, yA)。

如果某条信息导致矛盾（如 xA 和 xB 在同一集合），则该信息为假。

扩展域的优点是实现直观，不容易写错。缺点是空间需要开 k 倍。