0Pricing
Competitive Programming Academy · 课时

带路径压缩的 DSU

以近似常数时间执行查找与合并

带路径压缩的 DSU 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。

DSU 跟踪什么

并查集会将元素分组到互不重叠的集合中，因此您可以询问两个元素是否已经属于同一组。🤝

用树表示集合

DSU 将每个集合存储为一棵树。每个元素都指向一个父节点，而最顶层的节点，也就是根节点，是整个集合的唯一标识。

父节点数组

您可以将所有这些链接保存在一个数组中。开始时让每个元素以自身作为父节点，表示每个元素最初都独立属于一个集合。

parent = list(range(n))

查找根节点

find 操作会沿着父节点链接向上查找，直到某个元素指向自身。这个指向自身的节点就是标识该集合的根节点。

while parent[x] != x:
    x = parent[x]

过长的链会拖慢速度

如果不加处理，集合可能会形成又长又细的链。这样一来，find 就必须逐个节点遍历，单次查询可能耗时 O(n)，这会慢得无法接受。

引入路径压缩

路径压缩可以解决这个问题：查找根节点时，将每个访问过的节点都重新指向根节点，从而把树展平，以便下次使用。⚡

递归压缩

最简洁的方式是使用递归。找到根节点后，在返回之前将它保存回 parent[x]，这样链接就会被永久缩短。

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

两个元素属于同一集合吗

要测试两个元素是否连通，请比较它们的根节点。如果 find(a) 等于 find(b)，它们就属于同一组；否则它们仍然彼此分离。

if find(a) == find(b):
    print("connected")

合并两个集合

union 操作通过让一个根节点指向另一个根节点来合并集合。一行代码就能将两棵完整的树连接成一个集合。

def union(a, b):
    parent[find(a)] = find(b)

为什么如此快速

仅使用路径压缩时，操作的摊销复杂度大致为 O(log n)；再结合按秩合并后，每次查询都能达到近似常数的时间。

DSU 的用武之地

DSU 能够处理连通性问题：朋友圈、网络组件以及 Kruskal 最小生成树都依赖快速的 find 和 union。🌐

快速检查

请思考路径压缩实际上改变了什么。

回顾

您构建了一个DSU：使用父节点数组，通过 find 获取根节点，并通过 union 进行合并。路径压缩让它始终保持闪电般的速度。做得很好！🎉

常见问题解答

「带路径压缩的 DSU」课时是免费的吗？

是的 — 「带路径压缩的 DSU」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。

「带路径压缩的 DSU」这节课中我会学到什么？

以近似常数时间执行查找与合并 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Competitive Programming Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。

「带路径压缩的 DSU」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Competitive Programming Academy 课中编写并运行代码吗？

能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 带路径压缩的 DSU
  2. 按秩合并与连通分量
  3. Kruskal 最小生成树
  4. 使用堆实现 Prim 的 MST
← 返回 Competitive Programming Academy