按秩合并与连通分量
保持树扁平并统计分组
按秩合并与连通分量 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
union 可以很随意
普通的 union 只是将一个根节点挂到另一个根节点下。如果处理不当，就会形成又高又慢的树，因此我们需要更聪明的方式来合并根节点。
核心思想
按秩合并总是将较矮的树挂到较高的树下。保持树的高度较低，可以让之后的每次 find 都更快。📏
秩的含义
秩是对树高的估计。每个元素的初始秩为 0，因为单个节点下方没有更深的层级。
rank = [0] * n将较矮的树挂到较高的树下
比较两个根节点的秩。秩较小的根节点成为子节点，这样合并后的树就能尽可能保持扁平。
if rank[ra] < rank[rb]:
parent[ra] = rb相等时增加秩
当两个根节点的秩相等时，可以任选一个作为新根节点，并将它的秩加一，因为这棵树刚好增加了一层高度。
else:
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1按大小合并的变体
一种常见的替代方案是按大小合并：将较小的集合挂到较大的集合下。它同样有效，并且可以免费获得集合大小。
统计连通分量
将计数初始化为 n，因为每个元素都是独立的集合。每次成功的 union 将两个集合合并为一个，因此将计数减一。
components = n跳过无操作的 union
如果两个元素已经拥有相同的根节点，union 就不会执行任何操作。只有当它们的根节点确实不同时，才减少计数。
if find(a) != find(b):
union(a, b)
components -= 1秩与路径压缩结合
将按秩合并与路径压缩结合起来，DSU 的运行时间就是反阿克曼函数级别；对于任何实际输入而言，这基本上相当于常数时间。⚡
按需获取集合大小
使用按大小合并后，您可以立即回答任意集合有多大：只需读取该元素根节点处存储的大小。
group = size[find(x)]这些内容的应用场景
连通分量计数可以回答许多经典问题，例如好友圈数量，或在一系列合并调用后剩余的连通区域数量。🌐
快速检查
请思考连通分量计数器会如何变化。
回顾
您学习了按秩合并，以保持树的扁平，并学会了跟踪连通分量数量和组大小。DSU 现在快如闪电！🎉
常见问题解答
「按秩合并与连通分量」课时是免费的吗？
是的 — 「按秩合并与连通分量」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「按秩合并与连通分量」这节课中我会学到什么？
保持树扁平并统计分组 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「按秩合并与连通分量」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。