并查集 size 的优化

关键要点

• 研究表明，并查集的 size 优化通过维护集合大小来实现高效合并，平均时间复杂度接近常数 (O(\alpha(n)))。
• 证据倾向于 size 优化将小集合合并到大集合，保持树平衡，适合动态连通性问题。
• 存在争议：size 优化与 rank 优化效果相似，具体选择可能因场景而异。

---

直接回答

什么是 size 优化？
并查集（Union-Find）是一种用于管理不相交集合的数据结构，size 优化是一种提高合并（Union）操作效率的方法。它通过维护每个集合的大小（即包含的元素个数），在合并时总是将元素较少的集合连接到元素较多的集合上，从而保持树的高度较低。

如何工作？

• 维护一个 size 数组，size[i] 表示以 (i) 为根节点的集合包含的元素个数。
• 合并时，比较两个集合的 size 值，将较小的集合的根节点连接到较大的集合的根节点上，并更新 size。
• 例如，集合 A 有 3 个元素，集合 B 有 5 个元素，合并时将 A 连接到 B，B 的 size 更新为 8。

为什么有用？
研究表明，这种方法能减少树的高度，使查找和合并操作的平均时间复杂度接近常数 (O(\alpha(n)))，非常适合处理大规模动态连通性问题，如图的连通分量判断。

应用场景
size 优化常用于最小生成树算法（如 Kruskal 算法）和社交网络的连通性判断。

支持资源

• 并查集 size 的优化 | 菜鸟教程
• 并查集系列之「基于size的优化」 | 计算机科学论坛

---

---

并查集 size 优化的详细报告

背景与定义

并查集（Union-Find），也称为不相交集合数据结构，是一种树形的数据结构，主要用于处理动态连通性问题，如判断图中两个节点是否属于同一个连通分量，或在最小生成树算法（如 Kruskal 算法）中检测循环。研究表明，它通过一个数组表示一组森林，每棵树代表一个集合，树的根节点作为集合的代表元。

size 优化，具体来说是“按大小合并”（Union by Size），是一种优化 Union 操作的方法，旨在通过维护集合的大小来保持树的平衡，从而提高查找和合并的效率。多个来源（如 OI Wiki、CSDN 博客和菜鸟教程）指出，这种优化与路径压缩（Path Compression）和按秩合并（Union by Rank）一起，是并查集高效性的关键。

并查集的基本操作

并查集支持以下主要操作：

1. 初始化（Initialization）：
      – 每个元素最初自成一个集合，形成一棵只有根节点的树。
      – 实现上，使用数组 pa，初始时 pa[i] = i，表示每个元素是自己的父节点。
      – 同时，初始化 size 数组，size[i] = 1，表示每个集合初始包含 1 个元素。
2. 查找（Find）：
      – 查找操作的目标是找到某个元素的根节点，即集合的代表元。
      – 基本实现是通过递归或迭代向上遍历父节点，直到找到根节点（即 pa[x] == x）。
      – 示例代码（C++）：
        cpp int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); // 路径压缩 }
3. 合并（Union）：
      – 合并操作将两个集合合并成一个，通常是将一个集合的根节点连接到另一个集合的根节点。
      – 基本实现：
        cpp void unite(int x, int y) { pa[find(x)] = find(y); }
      – 未优化时，如果树深度过高，合并操作可能需要 (O(n)) 时间。

size 优化的原理

size 优化的核心思想是：在合并两个集合时，总是将元素较少的集合（即 size 较小的集合）连接到元素较多的集合（即 size 较大的集合）上，从而保持树的平衡，减少树的高度。

具体实现步骤：

• 维护一个 size 数组，其中 size[i] 表示以 (i) 为根节点的集合中包含的元素个数。
• 在合并操作时：
    – 找到两个集合的根节点 (root1 = find(x))，(root2 = find(y))。
    – 比较 size[root1] 和 size[root2]：
      – 如果 size[root1] < size[root2]，则将 (root1) 连接到 (root2) 上，即 pa[root1] = root2，并更新 size[root2] += size[root1]。
      – 否则，将 (root2) 连接到 (root1) 上，即 pa[root2] = root1，并更新 size[root1] += size[root2]。
• 确保合并后，树的深度不会显著增加。

例如，从 Learnku（web:7）中可以看到，size 优化通过维护 size 数组，确保小树连接到大树上，减少树的高度。例如，合并时选择方法二（小树挂大树）比方法一（大树挂小树）更优，因为树的高度从 4 层减少到 3 层。

示例分析

假设有一个并查集，初始状态为 5 个独立的集合：{0}, {1}, {2}, {3}, {4}，对应的父节点数组 parent 为 [0, 1, 2, 3, 4]，size 数组为 [1, 1, 1, 1, 1]。

• 步骤 1：合并 {0} 和 {1}。
    – size[0] = 1，size[1] = 1。
    – 由于相等，可以任意选择，假设将 0 连接到 1 上：parent[0] = 1，size[1] = 2。
    – 现在，parent = [1, 1, 2, 3, 4]，size = [1, 2, 1, 1, 1]。
• 步骤 2：合并 {1} 和 {2}。
    – size[1] = 2，size[2] = 1。
    – size[2] < size[1]，将 2 连接到 1 上：parent[2] = 1，size[1] = 3。
    – 现在，parent = [1, 1, 1, 3, 4]，size = [1, 3, 1, 1, 1]。
• 步骤 3：查找 2 的根节点。
    – 通过 parent 数组，2 的父节点是 1，1 的父节点是 1（根节点）。
    – 因此，2 的根节点是 1，时间复杂度为 (O(1))。

通过 size 优化，树的高度被控制在较低水平，确保了查找操作的高效性。

性能分析

• 未优化时：
    – 合并操作：最坏情况下 (O(n))（例如，形成一条长链）。
    – 查找操作：最坏情况下 (O(n))。
• size 优化后：
    – 合并和查找操作的平均时间复杂度为 (O(\alpha(n)))，其中 (\alpha(n)) 是逆阿克曼函数（几乎为常数）。
    – 空间复杂度为 (O(n))，用于存储父节点数组和 size 数组。

从 Exception（web:3）中可以看到，size 优化结合路径压缩后，可以使并查集在处理大规模动态连通性问题时表现更稳定，运行时间显著减少。

与其他优化的比较

• 路径压缩（Path Compression）：在查找过程中，将路径上的所有节点直接指向根节点，进一步减少树的高度。
• 按秩合并（Union by Rank）：类似于 size 优化，但使用树的高度（或其上界）来决定合并方向。

研究表明，size 优化和 rank 优化在效果上相似，但 size 优化更直观，因为它直接基于集合的大小，而 rank 优化需要维护树的高度。OI Wiki（web:6）提到，这两种方法都能有效控制树的高度，但具体选择可能因场景而异。

应用场景

size 优化广泛应用于以下场景：

• 动态连通性问题：判断图中两个节点是否连通，例如在无向图中查找连通分量。
• 最小生成树：在 Kruskal 算法中，用于检测添加边是否会形成循环。
• 社交网络：判断两个人是否通过朋友关系间接相连。
• 其他问题：如 NOI2001 的食物链问题、NOI2015 的程序自动分析等。

从 Runoob（web:1）中可以看到，size 优化能更高概率生成层数较低的树，特别适合处理大规模数据。

争议与局限

研究表明，并查集在合并和查询操作上非常高效，但存在一些争议：

• 未优化时，合并操作可能退化为 (O(n))，尤其在树深度过高时。
• 关于是否使用 size 优化还是 rank 优化，研究没有绝对共识，实际应用中两者效果相似，通常选择 size 优化更直观。
• 并查集不支持高效的集合分割操作，分割集合的复杂度较高。

表格总结

以下表格总结了 size 优化的主要特性：

特性	描述
优化目标	通过维护集合大小，保持树平衡，减少树的高度
实现方法	维护 size 数组，合并时小集合连接到大集合，更新 size 值
时间复杂度	平均 (O(\alpha(n)))，最坏 (O(n))（未优化）
空间复杂度	(O(n))
典型应用	动态连通性问题、最小生成树、社交网络连通性判断

参考资料

• 基于Size的并查集优化_扬俊的小屋-CSDN博客
• 并查集 size 的优化 | 菜鸟教程
• 并查集 size 的优化（超详细） – 异常教程
• 并查集 – OI Wiki
• 并查集系列之「基于size的优化」 | 计算机科学论坛

总结

并查集的 size 优化是一种简单有效的技术，通过在合并操作时优先将小集合合并到大集合中，保持树结构的平衡，显著提高了并查集的性能。这种优化结合路径压缩（path compression）技术，可以使并查集的操作效率接近常数级别，非常适合处理大规模动态连通性问题。