按秩合并与反阿克曼函数界
添加基于秩的合并以保持树的扁平，并理解两种优化结合后为何能达到 O(alpha(n)) 的均摊复杂度，即实际上为常数级。
按秩合并与反阿克曼函数界 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
没有秩时树为什么会变高
单独使用路径压缩只能在遍历之后防止树变高，但在最初的 union 操作期间，如果始终将较大树的根连接到较小树下面，仍然可能构建出一棵很高的树。按秩进行 union通过跟踪树高的上界（即秩），并始终将较浅的树连接到较深的树下面来解决这个问题。
秩并不完全等于树高——路径压缩可能使实际高度低于秩——但它是一个上界。让较深的树继续作为新根，可以确保只有在两棵秩相同的树合并时秩才会增加，从而将最大秩限制在 O(log n)。
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n # initially all trees have rank 0
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
# Attach lower-rank tree under higher-rank tree
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1 # only increases when ranks are equal
return True按秩进行 union 的三种情况
合并根节点为 px 和 py 的两个连通分量时，根据它们的秩会出现三种情况：
- rank[px] > rank[py]：将 py 连接到 px 下面——px 的秩不变
- rank[px] < rank[py]：将 px 连接到 py 下面——py 的秩不变
- rank[px] == rank[py]：将 py 连接到 px 下面（反之亦可）——新根的秩增加 1
秩只会在两者相等时增加。这意味着秩为 n 至少需要 2^n 个节点，因此最大秩为 O(log n)。即使不使用路径压缩，这也能让 find 路径保持较短。
# Illustrating rank behaviour with 8 nodes
dsu_parent = list(range(8))
dsu_rank = [0] * 8
def find(x):
while dsu_parent[x] != x:
x = dsu_parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py: return
if dsu_rank[px] < dsu_rank[py]:
px, py = py, px
dsu_parent[py] = px
if dsu_rank[px] == dsu_rank[py]:
dsu_rank[px] += 1
# Build balanced tree step by step
union(0,1); union(2,3); union(4,5); union(6,7)
union(0,2); union(4,6)
union(0,4)
print('Ranks:', dsu_rank) # max rank <= log2(8) = 3
print('Root of all:', find(0))路径压缩与按秩进行 union 的结合
同时使用路径压缩和按秩进行 union时，每次操作的摊还时间会降至O(alpha(n))，也就是反阿克曼函数。在任何实际输入规模下（最大可达 2^65536），alpha(n) 都不超过 4。这实际上就是常数时间。
路径压缩在遍历后自底向上地扁平化树，而按秩进行 union 则在合并期间从上到下阻止树变高。两者相辅相成：秩限制初始深度，压缩则在第一次遍历后消除这部分深度。
class OptimalDSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x): # path compression
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y): # union by rank
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
dsu = OptimalDSU(1000)
import random; random.seed(42)
for _ in range(5000):
dsu.union(random.randint(0,999), random.randint(0,999))
print('Max rank reached:', max(dsu.rank)) # stays very small理解反阿克曼函数
阿克曼函数 A(m, n) 增长得极其迅速——快于任何原始递归函数。它的逆函数alpha(n)被定义为满足 A(m, m) >= n 的最小 m。由于阿克曼函数增长极快，alpha(n) 的增长慢得难以想象。
当 n = 10^80（可观测宇宙中的原子数）时，alpha(n) 仍然只有 4。这就是为什么在所有实际场景中，同时采用两种优化的 DSU 都被视为近似常数时间。您永远不会遇到足够大的实际问题，使 alpha(n) 超过 5。
# Showing how slowly alpha(n) grows
# alpha(n) = smallest m such that A(m,m) >= n
# A(0,n) = n+1
# A(1,n) = n+2
# A(2,n) = 2n+3
# A(3,n) = 2^(n+3) - 3
# A(4,4) = 2^(2^(2^(2^2))) - 3 which is astronomically large
alpha_thresholds = {
1: 'n=1',
2: 'n up to 3',
3: 'n up to about 2048',
4: 'n up to 10^19728 (far beyond atoms in universe)',
5: 'essentially unreachable in practice',
}
for k, v in alpha_thresholds.items():
print(f'alpha(n)={k}: {v}')
print('\nConclusion: DSU operations are effectively O(1) for all real inputs.')秩与大小：该使用哪一个
按秩进行 union的替代方法是按大小进行 union：始终将较小的树连接到较大树下面。这两种方法都能保证树高为 O(log n)。按大小进行 union 通常更容易理解，因为大小是精确的计数，而秩是上界，在压缩之后可能无法反映真实树高。
在面试中，使用任一种方法都可以接受。按大小进行 union 的额外好处是可以直接获得连通分量大小，而许多问题都需要这个信息。按秩进行 union 在理论上略显优雅，也与塔扬关于反阿克曼函数复杂度界的原始证明相吻合。
class DSUBySize:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.size[px] < self.size[py]:
px, py = py, px # always attach smaller under larger
self.parent[py] = px
self.size[px] += self.size[py]
return True
dsu = DSUBySize(8)
for u, v in [(0,1),(2,3),(0,2),(4,5),(6,7),(4,6),(0,4)]:
dsu.union(u, v)
print('Size of giant component:', dsu.size[dsu.find(0)])证明概要：为什么秩保持在 O(log n)
我们可以通过归纳证明，秩为 r 的 DSU 树至少包含2^r个节点。基础情况：秩为 0 意味着只有一个节点（2^0 = 1）。归纳步骤：秩 r 只会在两棵秩为 r-1 的树合并时增加。根据归纳假设，每棵子树至少有 2^(r-1) 个节点，因此合并后的树至少有 2 × 2^(r-1) = 2^r 个节点。
由于秩为 r 的树至少包含 2^r 个节点，而总节点数为 n，因此最大秩至多为log₂(n)。这意味着不使用路径压缩时，find 需要 O(log n) 时间；使用路径压缩后，摊还成本会进一步大幅下降。
# Verify the 2^rank lower bound empirically
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return
if self.rank[px] < self.rank[py]: px, py = py, px
self.parent[py] = px
self.size[px] += self.size[py]
if self.rank[px] == self.rank[py]: self.rank[px] += 1
n = 32
dsu = DSU(n)
for i in range(n - 1): dsu.union(i, i + 1)
for root in range(n):
if dsu.find(root) == root:
r = dsu.rank[root]
print(f'Root {root}: rank={r}, size={dsu.size[root]}, 2^rank={2**r}')竞赛编程的 DSU 模板
在竞赛编程和面试中，您需要一个经过实战检验的 DSU 模板：代码简短、正确，并能处理所有边界情况。下面的模板使用路径减半（单遍压缩）结合按大小进行 union，这种组合易于快速输入，而且完全避免递归。
务必初始化 parent[i] = i 和 size[i] = 1。请记住，执行 find 后，根节点的 size 反映整个连通分量的大小。绝不要直接使用 size[x]，而应始终调用 size[find(x)]。
class DSU:
def __init__(self, n):
self.p = list(range(n))
self.sz = [1] * n
def find(self, x):
while self.p[x] != x:
self.p[x] = self.p[self.p[x]] # path halving
x = self.p[x]
return x
def union(self, x, y):
x, y = self.find(x), self.find(y)
if x == y: return False
if self.sz[x] < self.sz[y]: x, y = y, x
self.p[y] = x
self.sz[x] += self.sz[y]
return True
def same(self, x, y): return self.find(x) == self.find(y)
def size(self, x): return self.sz[self.find(x)]
# Usage
dsu = DSU(10)
dsu.union(0, 5)
dsu.union(5, 9)
print(dsu.same(0, 9)) # True
print(dsu.size(0)) # 3DSU 无法解决的情况
DSU 支持合并集合，但不支持将一个集合重新拆分为两个集合。如果问题同时要求合并和分离群组，您就需要使用其他数据结构（例如链切树）。DSU 也不会默认存储每个群组中的元素；您需要额外使用邻接表或字典来保存这些元素。
此外，标准 DSU 未经修改也不支持带权边（带权 DSU 是一种更高级的变体）。对于求相连节点之间最低代价路径这类问题，迪杰斯特拉算法或 BFS 更合适。了解 DSU 的适用范围可以避免错误地使用它。
# DSU is perfect for: connected-components, cycle detection,
# Kruskal's MST, accounts-merge, number-of-provinces
# DSU is NOT suitable for:
# - Splitting/removing edges from a group
# - Finding the actual path between two nodes
# - Storing all members of a group efficiently
# - Directed graphs (without modification)
# Example of storing group members alongside DSU
from collections import defaultdict
class DSUWithMembers:
def __init__(self, n):
self.p = list(range(n))
self.members = defaultdict(set)
for i in range(n): self.members[i].add(i)
def find(self, x):
while self.p[x] != x: self.p[x] = self.p[self.p[x]]; x = self.p[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return
self.members[px] |= self.members[py]
del self.members[py]
self.p[py] = px比较 DSU 与 BFS/DFS 的连通性
BFS/DFS 和 DSU 都能解决静态连通性查询，但各自的优势不同。BFS/DFS 的运行时间为 O(V + E)，并且能够找出节点之间的实际路径。DSU 可以在边集合逐步增长的情况下，以每次查询近似 O(1) 的代价回答大量连通性查询——非常适合在线算法，因为边会一次到达一条。
如果您一开始就收到所有边，并且只需要判断连通性，那么两者都可以。如果边是动态到达的，并且您需要在每条新边到达后回答连通性查询，DSU 显然更合适。对于还需要最短路径的问题，请使用 BFS。
# Comparing DSU vs BFS for 1000 nodes, 2000 edges
# After all edges given => BFS works fine
# But with online edge arrival + interleaved queries => DSU shines
from collections import deque
def bfs_connected(graph, src, dst, n):
visited = set([src])
q = deque([src])
while q:
node = q.popleft()
if node == dst: return True
for nb in graph.get(node, []):
if nb not in visited:
visited.add(nb); q.append(nb)
return False
# DSU for same query:
# dsu.same(src, dst) -- O(alpha(n)) amortised
# BFS for same query:
# O(V + E) every time -- not suitable for repeated queries
print('DSU is preferred for repeated connectivity queries.')
print('BFS/DFS is preferred when you also need the actual path.')练习：使用 DSU 求最小生成树
用于求最小生成树的克鲁斯卡尔算法直接使用 DSU。按权重对所有边执行 sort，然后如果一条边的两个端点属于不同的连通分量（不会形成环），就贪心地执行 add 操作。DSU 以近似 O(1) 的代价提供环检查。结果是一棵包含 n-1 条边的 MST。
这是展现 DSU 能力的经典例子：它将 O(E × V) 的朴素环检查转换为 O(E × alpha(n)) 的处理过程。加上 E log E 的排序，克鲁斯卡尔算法的总时间复杂度为 O(E log E)，而 DSU 操作非常快，与排序相比几乎可以忽略。
def kruskal(n, edges):
edges.sort(key=lambda e: e[2]) # sort by weight
parent = list(range(n))
rank = [0] * n
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py: return False
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
mst_weight = 0
mst_edges = []
for u, v, w in edges:
if union(u, v):
mst_weight += w
mst_edges.append((u, v, w))
return mst_weight, mst_edges
edges = [(0,1,4),(0,2,3),(1,2,1),(1,3,2),(2,3,5)]
w, e = kruskal(4, edges)
print('MST weight:', w) # 6: edges (1,2,1)+(1,3,2)+(0,2,3)
print('MST edges:', e)带 rollback 的 DSU：离线连通性
标准 DSU 不支持撤销操作。不过，支持 rollback 的 DSU（也称为带历史记录的 DSU）支持撤销：由于路径压缩很难撤销，因此只使用按秩执行 union 操作，并将每次 union 记录到栈中。执行 rollback 时，从栈中 pop 出记录，并恢复父节点和秩。这使我们能够解决边可能被添加和移除的离线动态连通性问题。
虽然这是标准面试中很少出现的高级变体，但它说明了按秩执行 union 操作才是关键不变量，而不是路径压缩。没有路径压缩时，每次 find 的时间复杂度为 O(log n)；结合 rollback，栈操作为 O(1)，因此总体上每次操作为 O(log n)，而不是 O(alpha(n))。
class DSUWithRollback:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.history = [] # stack of (node, old_parent, node2, old_rank)
def find(self, x): # NO path compression (cannot undo)
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return False
if self.rank[px] < self.rank[py]: px, py = py, px
# Record state before modifying
self.history.append((py, self.parent[py], px, self.rank[px]))
self.parent[py] = px
if self.rank[px] == self.rank[py]: self.rank[px] += 1
return True
def rollback(self):
py, old_par_py, px, old_rank_px = self.history.pop()
self.parent[py] = old_par_py
self.rank[px] = old_rank_px
dsu = DSUWithRollback(5)
dsu.union(0, 1); dsu.union(1, 2)
print('0 and 2 connected:', dsu.find(0) == dsu.find(2)) # True
dsu.rollback()
print('After rollback:', dsu.find(0) == dsu.find(2)) # False快速检查
请测试您对本课中“数据结构与算法——编程面试准备”概念的理解。
课程回顾
在本课中，您学到了：按秩执行 union 操作始终将较浅的树挂到较深的树下，只有当两棵秩相等的树合并时秩才会增加，从而使树高保持在 O(log n)，以及将路径压缩与按秩执行 union 操作结合起来可达到 O(alpha(n)) 的均摊复杂度——实际上是常数时间。接下来，我们将把完整的最优 DSU 应用于图中的冗余连接和环检测。
常见问题解答
「按秩合并与反阿克曼函数界」课时是免费的吗？
是的 — 「按秩合并与反阿克曼函数界」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「按秩合并与反阿克曼函数界」这节课中我会学到什么？
添加基于秩的合并以保持树的扁平，并理解两种优化结合后为何能达到 O(alpha(n)) 的均摊复杂度，即实际上为常数级。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「按秩合并与反阿克曼函数界」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 带路径压缩的 DSU
- 按秩合并与反阿克曼函数界
- 冗余连接与环检测
- 账户合并与连通分量