第 7 章 并查集

Disjoint Set

案例：设备网络不断增加连接

有 8 台设备，编号 0..7。开始时彼此没有连接，之后网络只会增加连线，不会删除已有连线。

系统不断收到两类请求：

• addEdge(u,v)：在设备 u、v 之间加入一条无向连接
• connected(u,v)?：询问此刻 u 与 v 是否存在一条路径相连

问题定义：只增边的动态连通问题

这类问题的状态是一张不断加边的无向图，查询可以穿插在任意两次加边之间。

例如，在先后加入 (0,1)、(2,3) 后，connected(0,3) 仍为 false；再加入 (1,2) 后，答案立刻变成 true。

关键限制是：只有加边，没有删边。 因此两个点一旦连通，以后就不会再次分开。

如果允许任意删边，单纯的并查集就不足以维护完整的动态连通性；本章研究的是只增边的情形。

为什么不每次都重新做深度优先 / 广度优先搜索？

深度优先搜索或广度优先搜索当然可以回答一次 connected(u,v)：从 u 出发搜索，看能否到达 v。

但连续查询时会重复计算。

学习目标

• 从只增边的动态连通案例抽象出不断合并的连通分量（connected component）
• 掌握 find、union、connected 三个操作及其关系
• 用森林（forest）与 parent[] 表示互不相交的集合
• 理解朴素合并为什么会制造长链
• 掌握按大小合并（union by size）与路径压缩（path compression）
• 能从结构变化解释复杂度如何改善到均摊（amortized）\(O(\alpha(n))\)
• 能把并查集用于动态连通性与最小生成树（minimum spanning tree）

本章路线图

并查集
集合合并与连通查询

动态连通案例
从加边与查询观察连通分量 集合抽象
只维护连通分量的划分（partition） 森林表示
一个根代表一个集合 性能问题
树高决定 find 成本 两次优化
按大小合并 · 路径压缩 典型应用
动态连通性 · 克鲁斯卡尔算法

从动态连通到集合合并

图上发生了什么：连通分量只会合并

一条连接如果跨越两个连通分量，就会把它们合并成一个更大的连通分量；如果两端本来已经连通，分量划分不变。

从连通分量到并查集

连通分量把所有顶点分成若干互不重叠的组

这些组只会合并，不会拆分

因此后续算法不必保存“0 到 6 具体走哪条路径”

只要维护每个顶点属于哪个组

数学抽象：划分与等价类（equivalence class）

设全集为

\[ U=\{0,1,\ldots,7\}. \]

一个 划分 是若干非空子集 \(C_1,C_2,\ldots,C_k\)，满足：

\[ C_i\cap C_j=\varnothing\quad(i\ne j), \qquad C_1\cup C_2\cup\cdots\cup C_k=U. \]

定义关系

\[ u\sim v \quad\Longleftrightarrow\quad u\text{ 与 }v\text{ 之间存在路径}. \]

它满足自反性（reflexive）、对称性（symmetric）和传递性（transitive），因此是一个 等价关系（equivalence relation）。每个连通分量正好是一个 等价类：

\[ [u]=\{v\in U\mid v\sim u\}. \]

代表元（representative）：给一个等价类一个名字

为了快速判断两个元素是否属于同一个等价类，可以让每个集合选一个 代表元。

例如当前划分是：

{0,1,2,3}    {4,5,6}    {7}
    ↑             ↑       ↑
  rep=0         rep=4   rep=7

每个集合选定一个元素作为代表元；只要这个选择保持一致，就可以用它标识当前集合。

并查集要支持什么？

现在把集合操作写成并查集的三个接口：

并查集操作	含义
find(x)	返回 x 所在等价类的代表元
union(a,b)	合并 a、b 所在的两个等价类
connected(a,b)	判断二者是否属于同一个等价类

connected(a, b)  <=>  find(a) == find(b)

union(a,b) 合并的是 a、b 所在的两个完整集合，不是只修改 a 与 b 这两个元素。

第一种想法：每个元素直接存所属集合

最直观的办法，是让每个元素直接保存自己的集合编号：

index    0  1  2  3  4  5  6  7
setId    A  A  A  A  B  B  B  C

这样查询集合编号很快；但如果一条新边把 B 与 A 连起来，就必须把 B 中所有成员的编号都改成 A。

结论：查询便宜，但一次集合合并可能要改写很多元素。

森林表示

能不能让一次合并只改一个位置？

如果每个集合用一棵树表示：

• 每个元素只保存一个父指针（parent pointer）
• 树根作为整个集合的代表元
• 两棵树合并时，只要让一个根指向另一个根

于是一次结构合并只需要修改 一个父指针。

关键不变量（invariant）：沿 parent 不断向上走，最终一定到达唯一的根；拥有同一个根的元素属于同一个集合。

森林与父指针数组

本章主实现统一使用 0-based 下标，并让 parent[] 始终只表示父指针：

parent[x] == x   => x 是根
parent[x] != x   => parent[x] 是 x 的父结点下标

朴素查找：find

先不做任何优化。find(x) 只做一件事：沿父指针一直走到根。

朴素查找：find 沿父指针找根

int find(int x) {
  Objects.checkIndex(x, parent.length);
  while (parent[x] != x) {
    x = parent[x];
  }
  return x;
}

find(…) 返回元素所属集合的代表元；允许压缩父指针，但不能改变集合划分本身。

并查集的森林不变量是：沿父指针不会离开当前连通分量，唯一指向自身的根就是代表元；因此 find 只需不断向根前进。

朴素 find 不改结构，所以本次经过多少条父指针边就付出多少成本，时间为 O(h)；若 union 把树拉成长链，重复查询也会重复付同样代价。

朴素合并：union

一次 union(a,b) 并不是简单地把 b 挂到 a。

必须先找到两个集合的根：

只有 ra != rb 时，才允许建立根到根的新父指针。

朴素合并：union 连接两个根

boolean union(int a, int b) {
  int rootA = find(a);
  int rootB = find(b);
  if (rootA == rootB) {
    return false;
  }
  parent[rootB] = rootA;
  return true;
}

union(…) 只合并两个不同代表元所在的集合；同集合输入不应制造新的父子关系。

union 先把两个参数归约为代表元；根相同说明它们已经属于同一等价类，再合并既无意义也会破坏后续的规模或秩统计。

只有根到根的连接才会把两棵旧树完整并成一棵；若改普通成员的父指针，只会移动它自己的子树，不能正确代表两个完整连通分量的合并。

性能问题

成本到底由什么决定？

对朴素森林来说：

• find(x)：沿根路径走，时间是 \(O(h)\)
• 已知两个根后，把一个根挂到另一个根：\(O(1)\)
• union(a,b)：本质上是两个 find 加一次根连接

所以问题全部集中到一个量：树高 \(h\)。

如果链接方向完全随意，\(h\) 最坏能有多大？

最坏情况：故意制造长链

如果依次把旧树挂到新的根下面，union(1,0), union(2,1), ..., union(6,5) 会把森林逐步拉成一条链。

长链的代价

最终 find(0) 需要走：

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6

因此最坏情况下：

\[ h=n-1,\qquad find=O(n) \]

第一次优化

第一次优化：按大小合并

策略只有一句：小树挂到大树下面，只让较小连通分量的结点整体增加一层。

为根记录集合大小

为了知道哪棵树更大，只增加一个 size[]：

parent[x]   始终表示父指针
size[root]  只在根位置有意义，记录整个集合大小

初始时：

parent[i] = i;
size[i] = 1;

若把 rb 挂到 ra：

parent[rb] = ra;
size[ra] += size[rb];

这样不需要改变 parent[] 的含义。

按大小合并：小树挂到大树

int find(int x) {
  Objects.checkIndex(x, parent.length);
  while (parent[x] != x) {
    x = parent[x];
  }
  return x;
}

boolean union(int a, int b) {
  int rootA = find(a);
  int rootB = find(b);
  if (rootA == rootB) {
    return false;
  }
  if (size[rootA] < size[rootB]) {
    int temporary = rootA;
    rootA = rootB;
    rootB = temporary;
  }
  parent[rootB] = rootA;
  size[rootA] += size[rootB];
  return true;
}

find(…) 返回元素所属集合的代表元；允许压缩父指针，但不能改变集合划分本身。

find 的代表元语义完全不变；按大小合并不改变集合定义，只约束根连接的方向来控制未来查找路径。

union(…) 只合并两个不同代表元所在的集合；同集合输入不应制造新的父子关系。

先比较两个代表元；若相同就不能再次合并或重复累计集合大小。只有不同根才代表两个真正不同的连通分量。

较小根挂到较大根后，只更新保留下来的根的集合大小；任一结点每加深一次时所在集合至少翻倍，所以树高最多 O(log n)。

为什么树高变成 \(O(\log n)\)？

看任意一个结点 x。

它的深度只有在 自己所在的整棵树被挂到另一棵树下面 时才会增加 1。

但按大小合并保证：另一棵树至少和它当前所在树一样大。

因此每当 x 的深度增加一次，它所在集合的大小至少翻倍：

\[ 1\rightarrow 2\rightarrow 4\rightarrow 8\rightarrow \cdots \]

最多翻倍 \(\log_2 n\) 次，所以树高被控制在：

\[ O(\log n) \]

第二次优化

还有重复工作：同一条路径会被反复走

按大小合并已经避免了极端长链，但 find 仍可能经过多个中间结点。

例如：

6 -> 4 -> 2 -> 1

第一次 find(6) 结束后，我们已经知道 6、4、2 的代表元都是 1。

下一次查询为什么还要重新走 6 -> 4 -> 2 -> 1？

这就引出路径压缩：让一次 find 顺便改善以后要访问的结构。

路径压缩：先找根，再在回程时改父指针

find(6) 先沿 6 -> 4 -> 2 -> 1 找到根，再在递归回程时按 2 -> 4 -> 6 的顺序更新父指针。

路径压缩：回程时压平路径

int find(int x) {
  Objects.checkIndex(x, parent.length);
  if (parent[x] != x) {
    parent[x] = find(parent[x]);
  }
  return parent[x];
}

find(…) 返回元素所属集合的代表元；允许压缩父指针，但不能改变集合划分本身。

只有指向自身的结点才是代表元；每次递归都沿父指针向根靠近，所以有限森林中必然终止，而越界元素不会进入这条父指针链。

递归返回的是同一连通分量的根，把沿途父指针直接改成这个代表元不会改变集合划分，只会缩短未来 find 的路径；与按大小合并合用后得到均摊 O(α(n))。

最终实现：状态、初始化与 find

final class DisjointSet {
  private final int[] parent;
  private final int[] size;

  DisjointSet(int n) {
    if (n < 0) {
      throw new IllegalArgumentException("n must be non-negative");
    }
    parent = new int[n];
    size = new int[n];
    for (int i = 0; i < n; i++) {
      parent[i] = i;
      size[i] = 1;
    }
  }

  int find(int x) {
    Objects.checkIndex(x, parent.length);
    if (parent[x] != x) {
      parent[x] = find(parent[x]);
    }
    return parent[x];
  }

DisjointSet 表示一组不断合并的互斥集合；类内操作只能改变森林形状或合并集合，不能制造重叠分区。

parent 决定集合森林，size 只在根上有决策意义；把结构与规模分开保存，既能找代表元，又能控制 union 的连接方向。

DisjointSet(n) 建立 n 个互不相交的单元素集合；每个元素初始都是自己的根，集合大小都为 1。

初始化让每个元素成为指向自身的根、集合大小为 1 的单元素集合，因此一开始就满足划分与规模不变量，后续只需保持它们。

find(…) 返回元素所属集合的代表元；允许压缩父指针，但不能改变集合划分本身。

find 递归到根后在回程压缩路径；改的是树形而不是集合划分，所以正确性不变，却能降低后续操作的均摊成本。

最终实现：union 与 connected

boolean union(int a, int b) {
  int rootA = find(a);
  int rootB = find(b);
  if (rootA == rootB) {
    return false;
  }
  if (size[rootA] < size[rootB]) {
    int temporary = rootA;
    rootA = rootB;
    rootB = temporary;
  }
  parent[rootB] = rootA;
  size[rootA] += size[rootB];
  return true;
}

boolean connected(int a, int b) {
  return find(a) == find(b);
}

union(…) 只合并两个不同代表元所在的集合；同集合输入不应制造新的父子关系。

两个 find 同时完成代表元查询和路径压缩；若根相同，说明连通关系早已成立，本次 union 不能再次改变集合大小。

根不同时按集合大小把小树挂到大树，再只更新保留下来的根的规模；这一处同时保持代表元语义和对数高度控制。

connected(…) 只比较两个元素的代表元，判断它们是否已经属于同一集合。

connected 不维护额外连通状态：两个元素属于同一连通分量当且仅当压缩后的代表元相同。

路径压缩以后，单次 find 是 \(O(1)\) 吗？

不是。

按大小合并已经保证树高至多 \(O(\log n)\)，因此一次尚未被压缩过的 find 仍可能走完整条根路径：

\[ T_{\text{single find}}=O(\log n) \]

路径压缩的收益在于：这次走过的路径会被改短，后面的操作因此更便宜。

所以 \(O(\alpha(n))\) 不是“每一次操作的最坏情况”，而是对 一串操作 做均摊分析后得到的平均均摊上界。

均摊分析：看一串操作

设并查集有 \(n\) 个元素，初始化之后执行 \(m\) 次 find / union / connected。

当同时使用 按大小合并 + 路径压缩 时，有经典结论：

\[ T(m,n)=O\!\left(m\alpha(n)\right) \]

因此每个操作的均摊代价为：

\[ O(\alpha(n)) \]

初始化两个数组还需要 \(O(n)\)，所以若把构造过程也算进去：

\[ O\!\left(n+m\alpha(n)\right) \]

union 和 connected 都只调用常数次 find，因此具有同样的均摊数量级。

为什么会出现 \(\alpha(n)\)：先从 \(O(\log n)\) 看起

只使用按大小合并时，一个结点每向下增加一层，它所在集合的规模至少翻倍。

如果一个结点最终位于深度 \(d\)，那么它所在集合至少经历了：

\[ 1,2,4,8,\ldots,2^d \]

因此 \(2^d\le n\)，也就是 \(d\le \log_2 n\)。这解释了为什么树高最多是 \(O(\log n)\)。

路径压缩又做了一件更强的事：一次 find 走过一条长路径后，会把沿途结点直接接到更高的祖先。这次走得远，会让以后走得更短。

所以接下来不能只盯着“一次 find 最长走多远”，而要计算：同一个结点在一串操作中，还会被重复经过多少次？

为什么会出现 \(\alpha(n)\)：一次走远，以后就少走

设一次 find(x) 经过了 x → p → q → ... → 根。回程时，路径压缩会把这些结点直接接向根。

这意味着：同一段长路径不会原样反复出现。 某个结点这次付出了较大的查找代价，下一次从它出发时，路径已经明显变短。

因此，分析不能把每次 find 都按当前树高单独收费；要把一长串操作放在一起，看一个结点还能多少次遇到“很远的父结点”。

为了计数，可以把父结点所在集合的规模分成越来越大的等级。一个结点若再次付出较高代价，它的父结点通常已经跳到了更高的等级；这种升级不可能无限发生。

直观上，等级边界会增长得非常快，例如：

\[ 1,\ 2,\ 4,\ 16,\ 65536,\ \ldots \]

这串数只用来说明“等级跨度越来越大”。严格证明使用阿克曼型函数（Ackermann-type function）构造分层；覆盖到规模 \(n\) 需要多少层，就由反阿克曼函数（inverse Ackermann function） \(\alpha(n)\) 描述。

\(\alpha(n)\) 到底有多慢？

阿克曼型函数增长得极快。反过来，\(\alpha(n)\) 问的是：要经过多少层这种快速增长，才能覆盖到 \(n\)？

所以即使 \(n\) 跨过极大的数量级，\(\alpha(n)\) 也只会增加很小的整数。

把所有 find 的父指针访问合在一起计算，得到：

\[ T(m,n)=O\!\left(m\alpha(n)\right) \]

因此单次操作的均摊代价是 \(O(\alpha(n))\)；它非常接近常数，但严格来说仍不是 \(O(1)\)。

复杂度：我们刚刚经历了什么？

实现	单次操作最坏情况	一串操作的均摊代价
任意方向合并	\(O(n)\)	\(O(n)\)
按大小合并	\(O(\log n)\)	\(O(\log n)\)
按大小合并 + 路径压缩	\(O(\log n)\)	\(O(\alpha(n))\)

这里的 \(\alpha(n)\) 是反阿克曼函数，增长极慢。

“接近常数”是工程直觉；严格复杂度仍写作均摊 \(O(\alpha(n))\)。

边界：并查集不是什么都能做

普通并查集非常适合：

操作	支持
新增关系 / 加边	✓
合并两个连通分量	✓
查询是否同组	✓
删除一条边后自动拆分连通分量	✗

删除边可能让一个连通分量分裂成多个集合，而普通 union / find 没有“拆分”操作。

因此这里解决的是只增边的动态连通问题，不是可以任意加边、删边的一般动态连通问题。

应用

应用一：问题定义——只增边的动态连通

给定一张无向图，初始时可以没有边。之后只会不断加入新边，并在任意时刻询问两个顶点是否连通。

需要支持两类操作：

addEdge(u,v)       加入一条边
connected(u,v)     查询 u、v 当前是否连通

应用一：分析——真正需要维护什么？

如果每次查询都重新做深度优先搜索或广度优先搜索，会反复发现已经知道的连通关系。

由于这里只加边、不删边，连通分量只会合并。因此真正需要长期保存的状态不是每条搜索路径，而是当前的连通分量划分。

应用一：解法——用并查集维护连通分量

每加入一条边，就合并它两端所在的集合；每次查询，只比较两个端点的代表元：

addEdge(u,v)       -> union(u,v)
connected(u,v)     -> connected(u,v)

已经形成的连通分量由并查集直接保留下来，不必为每次查询重新遍历整张图。

应用一：代码对应

static final class DynamicConnectivity {
  private final DisjointSet ds;

  DynamicConnectivity(int vertexCount) {
    ds = new DisjointSet(vertexCount);
  }

  void addEdge(int u, int v) {
    ds.union(u, v);
  }

  boolean connected(int u, int v) {
    return ds.connected(u, v);
  }
}

DynamicConnectivity 用并查集保存当前连通分量；新增边只会合并集合，不会拆分已有连通关系。

ds 是唯一持久状态；它记录截至当前所有已加入边诱导出的连通分量，而不是保存边本身。

DynamicConnectivity(vertexCount) 从没有边的图开始，因此每个顶点初始都是独立连通分量。

对象只持有一个并查集，它持续保存“截至目前所有已加入边”形成的连通分量划分；状态跨操作保留，因此不必反复重建连通信息。

addEdge(u,v) 把新边的连通效果压缩成一次 union；它只可能合并两个连通分量，不会拆分任何已有连通分量。

新增边只需 union(u,v)：若两端原本不同组就合并，若已经同组结构自然不变。这正适合只增边的动态连通问题。

connected(…) 只比较两个元素的代表元，判断它们是否已经属于同一集合。

查询直接比较两个代表元；代价来自并查集的均摊查找，而不是重新在整张图上运行深度优先搜索或广度优先搜索。

应用二：问题定义——最小生成树

给定一张连通、无向、带权图，希望选出一部分边，使所有顶点仍然连通，同时边权总和尽可能小。

如果图有 \(V\) 个顶点，那么最终需要得到一棵包含全部顶点、恰有 \(V-1\) 条边的树。这就是最小生成树（minimum spanning tree，MST）问题。

应用二：分析——一条候选边能不能加入？

假设已经选出的边构成一片森林。现在考虑候选边 (u,v)：

• 如果 u、v 已经在同一个连通分量中，再加入这条边就会形成环（cycle）；
• 如果 u、v 属于不同连通分量，这条边会把两个分量连接起来，不会形成环。

所以每考虑一条边，都需要快速回答：两个端点当前是否已经连通？

应用二：解法——用并查集判环

把所有边按权重从小到大处理。对每条边 (u,v)：

find(u) == find(v)   -> 跳过：加入会成环
find(u) != find(v)   -> 接受，并执行 union(u,v)

这样，并查集负责维护“当前已经连成哪些分量”；边权顺序负责决定先考虑哪条边。

这套贪心算法称为克鲁斯卡尔算法（Kruskal）。

克鲁斯卡尔算法：完整执行

边按权重从小到大被检查；并查集记录当前生成森林的连通分量。

克鲁斯卡尔算法：选边、判环与提前结束

static List<Edge> kruskal(int n, List<Edge> edges) {
  if (n < 0) {
    throw new IllegalArgumentException("n must be non-negative");
  }
  ArrayList<Edge> sorted = new ArrayList<>(edges);
  sorted.sort(Comparator.comparingInt(Edge::weight));
  DisjointSet ds = new DisjointSet(n);
  ArrayList<Edge> tree = new ArrayList<>(Math.max(0, n - 1));
  for (Edge edge : sorted) {
    if (edge.u() < 0 || edge.u() >= n || edge.v() < 0 || edge.v() >= n) {
      throw new IndexOutOfBoundsException("edge endpoint outside graph");
    }
    if (ds.union(edge.u(), edge.v())) {
      tree.add(edge);
      if (tree.size() == n - 1) {
        break;
      }
    }
  }
  if (n > 0 && tree.size() != n - 1) {
    throw new IllegalArgumentException("graph is disconnected");
  }
  return List.copyOf(tree);
}

kruskal(…) 按边权从小到大选安全边；并查集用来判断加入当前边是否会形成环。

按权重升序处理边，把“下一条可能安全的轻边”变成单调扫描；并查集只维护当前生成森林的连通分量，不负责证明权重最优。

候选边端点必须与并查集元素一一对应；否则代表元就不能继续表示图中顶点的连通分量，判环失去依据。

union(u,v) 成功表示该边连接两个不同连通分量，因此加入后不会成环；边权顺序则保证优先考虑更轻的候选边。

达到 n-1 条无环边即可停止；若所有边检查完仍不足 n-1 条，则说明输入图不连通。

“无环且 n-1 条”只能说明得到一棵生成树；最小性来自克鲁斯卡尔算法按边权递增选择可接受边的贪心策略。

克鲁斯卡尔算法：时间与空间复杂度

设图有 \(V\) 个顶点、\(E\) 条边。

阶段	成本
按权重排序全部边	\(O(E\log E)\)
初始化并查集	\(O(V)\)
最多检查 \(E\) 条边，每条做一次 union	均摊 \(O(E\alpha(V))\)

因此总时间为：

\[ O\!\left(E\log E + E\alpha(V) + V\right) \]

对通常的连通图，\(E\ge V-1\)，且比较排序（comparison sort）的 \(E\log E\) 项占主导，因此常写成：

\[ O(E\log E) \]

并查集自身空间是 \(O(V)\)；若把输入边列表与输出的最小生成树也算入存储，则分别还需要 \(O(E)\) 与 \(O(V)\)。

补充：其它常见表示与策略

本章主线固定使用：

parent[root] == root    根指向自己
size[root]              记录集合大小
按大小合并 + 路径压缩

教材和其它实现中还常见两种写法：

• 按秩合并（union by rank）：保存树高的近似上界，而不是精确集合大小；目标仍然是避免把较高的树挂到较矮的树下面
• 负根元数据：让 parent[root] 保存负的集合大小或秩，从而把元数据压进同一个数组

它们都可以得到同一类高效并查集；本章不再用第二份完整实现打断主线。

本章小结

• 只增边的动态连通问题可以抽象为若干连通分量，查询只关心两个元素是否属于同一集合。
• find 返回集合代表元，union 合并两个集合，connected 用两个代表元是否相同给出判断。
• 并查集用森林表示集合，并用 parent[] 把每个元素指向父节点或自身代表元。
• 朴素合并若反复把大树挂到小树下，会制造长链，使 find 退化到线性时间。
• 按大小合并控制树高增长，路径压缩在 find 回程时把路径节点直接接近根。
• 复杂度改善来自树形结构持续变扁；两种优化合用后单次操作达到均摊 \(O(\alpha(n))\)。

下载本章完整 Gradle 工程

本章习题

• 习题 1：集合合并：从 {0},{1},{2},{3},{4} 开始，依次执行 union(0,1)、union(2,3)、union(1,2)，写出每一步连通分量。
• 习题 2：路径压缩回程顺序：若 6 -> 4 -> 2 -> 1，使用本章递归 find(6) 后，parent[2]、parent[4]、parent[6] 按什么顺序更新？最终分别是什么？
• 习题 3：克鲁斯卡尔算法与成环判断：说明为什么 union(u,v) 返回 false 时，克鲁斯卡尔算法必须跳过候选边 (u,v)。

致谢

谢谢

sqlite@nju.edu.cn
https://slab-nju.cn

石守谦