带路径压缩的 DSU
实现带路径压缩的查找操作，使路径上的所有节点都直接指向根节点，从而使查找操作的均摊复杂度达到近似 O(1)。
带路径压缩的 DSU 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
什么是并查集
并查集（DSU）也称为并查集，是一种维护互不相交（不重叠）集合的数据结构。它支持两个核心操作：find（元素 x 属于哪个集合？）和 union（合并包含 x 和 y 的集合）。DSU 非常适合动态连通性问题：各个组会随时间合并，但不会拆分。
每个元素最初都属于自己的集合。在处理边或关系时，我们会逐步合并集合。挑战在于如何高效完成这些操作——朴素实现每次操作需要 O(n)，但经过优化后，可以达到接近 O(1) 的均摊复杂度。
# Naive DSU without optimisations
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # each node is its own parent
def find(self, x):
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:
self.parent[px] = py朴素 find 的问题
在朴素 DSU 中，find(x) 会沿着父节点链向上遍历，直到到达一个指向自身的节点（根节点）。如果树是平衡的，这一过程的复杂度是 O(log n)。但是，如果我们始终将第二个根连接到第一个根的下面来执行 union，就可能创建一条长度为 n 的链（退化树），使每次 find 的复杂度达到 O(n)。
考虑依次合并 0→1→2→3→4。节点 0 的 find 调用必须遍历整条链。借助路径压缩，我们可以在 find 操作本身进行期间，让每个访问过的节点都直接指向根节点，从而消除这个问题。
# Worst case without compression: a chain
# parent = [1, 2, 3, 4, 4] => find(0) takes 4 steps
# After path compression: parent = [4, 4, 4, 4, 4] => find(0) takes 1 step
parent = [1, 2, 3, 4, 4]
print('Before:', parent)
# Simulate find(0) with naive approach
x = 0
steps = 0
while parent[x] != x:
x = parent[x]
steps += 1
print('Root:', x, 'Steps taken:', steps)路径压缩：单遍递归
路径压缩会修改 find 操作，使其找到根节点后，将路径上的每个节点更新为直接指向根节点。之后对这些节点执行 find 时，复杂度将变为 O(1)。递归版本只需一次遍历就能优雅地实现这一点。
关键思路是：递归调用返回根节点后，在返回之前设置 self.parent[x] = root。这样就能将树扁平化——搜索路径上的所有节点现在都直接指向根节点。这不会改变节点所属的集合，只会缩短以后查找时所需经过的路径。
class DSU:
def __init__(self, n):
self.parent = list(range(n))
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:
self.parent[px] = py
dsu = DSU(5)
dsu.union(0, 1)
dsu.union(1, 2)
dsu.union(2, 3)
print('Root of 0:', dsu.find(0))
print('Parent array after compression:', dsu.parent)路径压缩：双遍迭代
路径压缩的迭代版本使用两次遍历：第一次向上遍历以找到根节点；第二次重新访问路径上的每个节点，并将其父节点直接更新为根节点。这样可以避免递归栈开销，在接近 Python 递归深度上限的极深树上也很安全。
无论采用递归方法还是迭代方法，正确性都不变——find 仍然返回相同的根节点。唯一的区别是，父节点指针会作为副作用被更新，使以后对这些节点执行 find 时的复杂度达到 O(1)。
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
root = x
while self.parent[root] != root:
root = self.parent[root] # first pass: find root
while self.parent[x] != root:
nxt = self.parent[x]
self.parent[x] = root # second pass: compress
x = nxt
return root
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
return True
return False # already connected
dsu = DSU(6)
for a, b in [(0,1),(1,2),(2,3),(3,4)]:
dsu.union(a, b)
print('Parent before find(0):', dsu.parent[:])
dsu.find(0)
print('Parent after find(0):', dsu.parent[:])路径压缩的摊还复杂度
单独使用路径压缩时，在包含 m 次操作的序列中，每次操作的摊还时间复杂度为O(log n)。每次 find 在首次遍历一条链时可能代价较高，但它会将这条链扁平化，因此之后对这些节点执行 find 时的复杂度都是 O(1)。总工作量会分摊到多次操作中。
形式化分析使用势函数法：每当节点的父节点路径变短时，DSU 的势能就会下降，而这部分下降的势能可以支付遍历成本。不使用按秩进行 union 时，单独的路径压缩也能达到 O(log n) 的摊还复杂度，这已经比朴素方法的 O(n) 有了巨大改进。
# Demonstrating amortised benefit
import time
def build_chain(n):
parent = list(range(n))
for i in range(n - 1):
parent[i] = i + 1 # chain: 0->1->2->...->n-1
return parent
n = 1000
parent = build_chain(n)
# First find on a chain: visits n nodes
x = 0
root = x
while parent[root] != root:
root = parent[root]
# Compress
while parent[x] != root:
nxt = parent[x]; parent[x] = root; x = nxt
print('After first find, parent[0]:', parent[0]) # should be n-1
print('Second find cost: O(1) since parent[0] is now the root')连通分量计数
DSU 的一个常见应用是在图中统计连通分量。我们将 components 计数器初始化为 n（每个节点对应一个）。每次成功执行 union（合并两个不同的集合）时，都将计数器减 1。最后，计数器中保存的就是不同连通分量的数量。
与使用 BFS 或 DFS 处理连通性查询相比，这种方法效率更高，尤其适用于边逐步到达的情况（在线处理）。无论边在何时到达，DSU 处理每条边的摊还时间都接近 O(1)。
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.components = 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
self.parent[px] = py
self.components -= 1
return True
dsu = DSU(7)
edges = [(0,1),(1,2),(3,4),(5,6)]
for u, v in edges:
dsu.union(u, v)
print('Components:', dsu.components) # 4: {0,1,2}, {3,4}, {5,6}, {6 alone was merged}
# Node 6 is alone => 4 total: {0,1,2},{3,4},{5,6},{6} wait
# Let me recalculate: 7 nodes, 4 edges merged 4 pairs => 7-4=3... no
# {0,1,2} one union, {3,4} one, {5,6} one => 7-3=4 components
print('Expected: 4')图问题中的 DSU：省份数量
省份数量问题给出一个 n×n 邻接矩阵，并要求计算存在多少组直接或间接相连的城市。这正是连通分量问题，使用 DSU 可以简洁地解决。我们遍历所有满足 isConnected[i][j] == 1 的节点对 (i, j)，并调用 union(i, j)。
处理完所有连接后，dsu.components 就是答案。与从每个未访问节点开始运行 BFS 相比，这种方法更简单、更快速，而且可以直接处理矩阵表示，无需先构建邻接表。
def find_provinces(isConnected):
n = len(isConnected)
parent = list(range(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:
parent[px] = py
return True
return False
count = n
for i in range(n):
for j in range(i + 1, n):
if isConnected[i][j] == 1:
if union(i, j):
count -= 1
return count
matrix = [[1,1,0],[1,1,0],[0,0,1]]
print(find_provinces(matrix)) # 2: cities {0,1} and {2}路径压缩变体：减半
除了双遍压缩，还有一种更简单的单遍变体，称为路径减半：沿链向上遍历时，让每个节点指向其祖父节点而不是父节点。这样无需第二次遍历，每次遍历都能将路径长度减半；与按秩进行 union 结合时，它能达到相同的 O(alpha(n)) 摊还复杂度。
在竞赛编程中，人们通常更喜欢路径减半，因为它只需一个简洁的循环，不需要递归或第二次遍历。每一步执行 self.parent[x] = self.parent[self.parent[x]]; x = self.parent[x]。
class DSUHalving:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # point to grandparent
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
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
dsu = DSUHalving(8)
for u, v in [(0,1),(2,3),(4,5),(6,7),(0,2),(4,6),(0,4)]:
dsu.union(u, v)
print('All in one component:', dsu.find(0) == dsu.find(7))执行 union 后检查连通性
要检查两个节点是否connected（属于同一个连通分量），请调用 find(x) == find(y)。如果两次调用都返回相同的根节点，它们就属于同一个连通分量。这就是connected查询；借助路径压缩，其摊还时间复杂度接近 O(1)。
在面试题中，连通性查询通常会与 union 操作交错出现。DSU 可以在线处理这两类操作——您可以按任意顺序交替执行 union 和查询。这一点使 DSU 区别于 BFS/DFS 等静态图算法，后者必须在每次结构发生变化后重新运行。
class DSU:
def __init__(self, n):
self.parent = list(range(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:
self.parent[px] = py
def connected(self, x, y):
return self.find(x) == self.find(y)
dsu = DSU(10)
dsu.union(0, 3)
dsu.union(3, 7)
dsu.union(1, 5)
print(dsu.connected(0, 7)) # True: 0-3-7
print(dsu.connected(0, 5)) # False: different components
print(dsu.connected(1, 5)) # True: 1-5DSU 实现中的常见陷阱
一个常见错误是调用 find 后错误地修改 parent。在检查是否相等之前，务必对两个元素都调用 find，否则可能错误地将一个节点与它自己的根节点进行比较。另一个常见陷阱是忘记：当两个元素已经共享同一个根节点时，union 应该不执行任何操作。
在 Python 中，递归深度上限（默认值为 1000）可能导致使用递归 find 处理大型链时出现 RecursionError。您可以改用迭代双遍版本，使用 sys.setrecursionlimit 提高上限，或者使用迭代的路径减半，以彻底避免深度递归。
import sys
sys.setrecursionlimit(10000) # needed for large recursive DSU
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
# Safe iterative path compression
root = x
while self.parent[root] != root:
root = self.parent[root]
while self.parent[x] != root:
nxt = self.parent[x]
self.parent[x] = root
x = nxt
return root
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False # already same component — do nothing
self.parent[px] = py
return True
dsu = DSU(5)
print(dsu.union(0, 1)) # True: merged
print(dsu.union(0, 1)) # False: already merged — no double-countingDSU 大小跟踪
在某些问题中，您需要知道每个连通分量的大小，而不仅仅是它的根节点。添加一个初始化为全 1 的 size 数组。合并两个连通分量时，将较小根节点对应的大小加到较大根节点上。这样，在任意 union 之后，都可以用 O(1) 的时间查询连通分量大小。
大小跟踪也是按大小进行 union的基础（这是按秩进行 union 的替代方法）：始终将较小的树连接到较大树的根节点下。这可以保证树高保持在 O(log n)，从而获得与按秩进行 union 相同的渐进复杂度保证。
class DSUWithSize:
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
if self.size[px] < self.size[py]:
px, py = py, px # attach smaller under larger
self.parent[py] = px
self.size[px] += self.size[py]
def get_size(self, x):
return self.size[self.find(x)]
dsu = DSUWithSize(6)
for u, v in [(0,1),(1,2),(3,4)]:
dsu.union(u, v)
print('Size of component containing 0:', dsu.get_size(0)) # 3
print('Size of component containing 3:', dsu.get_size(3)) # 2
print('Size of component containing 5:', dsu.get_size(5)) # 1快速检查
测试您对本课数据结构与算法—编程面试准备相关概念的理解。
课程回顾
本课中您学到了：DSU 通过 find 和 union 操作维护不相交集合，路径压缩通过让所有经过的节点直接指向根节点来扁平化树，并且这会使 find 的摊还性能接近 O(1)。接下来我们将探讨按秩进行 union，它从上到下保持树的浅层结构，以达到反阿克曼函数的复杂度界。
常见问题解答
「带路径压缩的 DSU」课时是免费的吗？
是的 — 「带路径压缩的 DSU」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「带路径压缩的 DSU」这节课中我会学到什么？
实现带路径压缩的查找操作，使路径上的所有节点都直接指向根节点，从而使查找操作的均摊复杂度达到近似 O(1)。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「带路径压缩的 DSU」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 带路径压缩的 DSU
- 按秩合并与反阿克曼函数界
- 冗余连接与环检测
- 账户合并与连通分量