如何基于源与目标对数字分组？DSA求解方法咨询

你的问题本质是统计无向图的连通分量数量，或者更精准地说，是不相交集合的分组计数问题，最适合用**并查集（Union-Find/Disjoint Set Union, DSU）**这个数据结构解决——这是DSA里处理这类合并、查询分组问题的标准工具。

核心概念：并查集 #

并查集的核心是维护一组不相交的集合，支持两个关键操作：

• find：查找某个元素所属集合的根节点（通过路径压缩优化，让后续查询更快）
• union：将两个元素所在的集合合并（通过按秩/大小合并优化，避免集合树结构过深）

问题对应关系 #

• 每一对输入的数字，相当于一条无向边，代表这两个元素属于同一个分组
• 最终需要统计的分组数，就是所有元素中不同根节点的数量（即连通分量的个数）

结合测试用例理解 #

• 测试用例1：5对数字把所有涉及的元素分成2个独立集合：{2,3}、{1,4,5,6,7}，所以输出2
• 测试用例2：6对数字形成5个独立集合：{2,4}、{3,1}、{7,6,5}、{9,8}、{22,32}，所以输出5

新手入门步骤 #

1. 先手动模拟：拿测试用例的元素一步步模拟find和union操作，搞懂集合合并的逻辑
2. 实现基础版并查集：先写不带优化的版本，再加上路径压缩和按秩合并（这两个优化能把操作时间复杂度降到近似O(1)）
3. 统计分组数：收集所有出现过的元素，遍历每个元素用find找到根，去重后计数就是结果
4. 适配大元素范围：如果元素数值很大（比如22、32这种），用哈希表（比如Python的dict）存储父节点，不要用数组浪费空间

内容的提问来源于stack exchange，提问作者Ragul Shanmugarajan