集合合并算法详解：从反复扫描到并查集的高效实现-北京尧图网络

1. 从一个集合合并题说起这到底在考什么第一次看到{aaa,bbb,ccc},{bbb,ddd},{eee,fff},{ggg},{ddd,hhh}这串东西很多人第一反应是“不就是把有交集的集合粘在一起吗”。真动手写代码才发现坑比想象中多{bbb,ddd}和{ddd,hhh}要并成{bbb,ddd,hhh}而{bbb,ddd,hhh}又和{aaa,bbb,ccc}有公共元素bbb于是三组最终要合成{aaa,bbb,ccc,ddd,hhh}。剩下{eee,fff}和{ggg}各自独立谁也不挨着谁。这个运算在计算机科学里有正式名字叫集合合并也叫不相交集合的并查集Union-Find问题或者更通俗点叫传递闭包式合并。它的核心逻辑只有一句话只要两个集合有公共元素它们就属于同一个连通分量必须合并合并后的新集合还要继续参与后续比较直到没有任何两个集合存在交集为止。我之所以想专门写这篇是因为这个看似简单的运算在实际工程里出现的频率高得离谱。数据库里做跨表合并要去重、前端做标签聚合要归并、图论里找连通分量、社交网络里找朋友圈、甚至整理一份混乱的通讯录底层都是同一套逻辑。热搜词里“跨表合并”“git分支合并”“合并两个有序的单链表”“基于链表的两个集合的差集”这些本质上都在处理“合并”这件事的不同变体。这篇文章适合谁看如果你是刚学数据结构的学生正在被并查集或者集合运算折磨这篇能帮你把思路彻底理顺如果你是工作两三年的开发者需要处理数据清洗、标签归并、连通性判断这类需求这篇能给你一套可直接抄作业的实现方案如果你只是好奇“这么个小题有什么好讲的”那不妨往下看我会把里面藏着的几个经典陷阱一个个挖出来。先明确一下输入和输出。输入是若干集合{aaa,bbb,ccc}、{bbb,ddd}、{eee,fff}、{ggg}、{ddd,hhh}。输出是合并后的结果{aaa,bbb,ccc,ddd,hhh}、{eee,fff}、{ggg}。注意输出的顺序和分组这不是随便排的而是严格按照“连通性”来划分的。下面我会从设计思路、核心算法、实操实现、踩坑排查四个层面把这个运算彻底讲透。2. 整体设计思路为什么不能一遍扫完就完事2.1 最直觉的做法为什么容易翻车拿到这组数据最朴素的想法是从左到右遍历拿第一个集合{aaa,bbb,ccc}去和后面的比发现和{bbb,ddd}有交集bbb合并成{aaa,bbb,ccc,ddd}继续拿这个新集合去比发现和{ddd,hhh}有交集ddd再合并成{aaa,bbb,ccc,ddd,hhh}然后处理{eee,fff}和谁都无交集单独成组最后{ggg}也单独成组。这个思路本身没错但它有一个致命前提你必须保证每个合并后的新集合都要重新和所有还没处理过的集合比一遍。为什么因为合并会让集合“长大”长大之后可能和原本不相干的集合产生新的交集。举个反例假设输入是{a,b}、{c,d}、{b,c}。如果按顺序先合并前两个发现无交集各自保留再拿{a,b}和{b,c}比合并成{a,b,c}这时候{c,d}其实和{a,b,c}有交集c但如果你已经跳过了{c,d}就会漏合并。所以第一版设计的关键点是外层循环要反复扫描直到某一轮没有任何合并发生为止。这就是所谓的“不动点迭代”。很多新手写集合合并写完发现结果少合并了一组八成就是这里出了问题。2.2 并查集更优雅的解法反复扫描虽然能出结果但时间复杂度是 O(n²) 甚至 O(n³)数据量一大就扛不住。工程上更常用的方案是并查集Union-Find它的思路是把每个“元素”看成一个节点同一个集合里的元素互相连通。合并两个集合本质上就是把两个连通分量接在一起。具体到这个例子所有出现的元素是aaa, bbb, ccc, ddd, eee, fff, ggg, hhh。我们先把每个元素初始化成独立的父节点然后遍历每个集合把集合内所有元素 union 到一起。比如处理{aaa,bbb,ccc}就让bbb和aaa合并、ccc和aaa合并处理{bbb,ddd}发现bbb和ddd已经在同一棵树里了因为bbb连着aaa于是ddd也挂到aaa下面处理{ddd,hhh}hhh也挂进来。最后按根节点分组就得到{aaa,bbb,ccc,ddd,hhh}、{eee,fff}、{ggg}。并查集的优势在于每个元素只处理常数次加上路径压缩和按秩合并均摊复杂度接近 O(α(n))α 是反阿克曼函数实际应用中几乎等于常数。数据量上万、上百万时这个差距是数量级的。2.3 两种方案的取舍那是不是无脑选并查集也不是。我实际用下来选择依据主要看两点场景推荐方案理由集合数量少几十个以内元素类型复杂反复扫描合并代码直观不用建映射表调试方便集合数量大元素可哈希并查集性能碾压适合生产环境需要保留合并过程日志反复扫描每轮合并可记录便于追溯元素是对象、不可直接比较并查集哈希映射先给每个对象分配 ID再 union提示如果元素本身是字符串或数字并查集直接用哈希表做 ID 映射即可如果是复杂对象建议先序列化成唯一键再走并查集否则比较逻辑会拖慢整体性能。还有一个容易被忽略的点合并的方向性。有些业务场景要求合并后的集合保持某种顺序比如按字典序、按插入顺序这时候并查集只负责分组排序要单独做一遍。我在做标签归并时就遇到过产品要求合并后的标签按热度排序结果并查集分完组还得再排一次多了一步但逻辑清晰。3. 核心细节解析元素、连通性与合并顺序3.1 元素粒度决定合并结果先问一个问题{aaa,bbb,ccc}和{bbb,ddd}能合并是因为它们共享元素bbb。那如果两个集合共享的是“部分匹配”呢比如{user_001}和{user_001_admin}算不算有交集这取决于你对“元素”的定义。在标准集合运算里元素是原子单位user_001和user_001_admin是两个完全不同的元素不构成交集。但实际业务里经常需要做“前缀匹配合并”或“模糊合并”这就超出了标准集合运算的范畴。我的建议是先把业务规则想清楚再决定元素粒度。如果确实需要模糊匹配就在合并前做一轮归一化把user_001_admin映射成user_001再走标准流程。这个例子里元素都是aaa、bbb这种短标识粒度清晰不存在歧义。但你要知道真实项目里“什么算同一个元素”往往是最耗时的决策而不是算法本身。3.2 连通性的传递性集合合并的本质是连通性。{aaa,bbb,ccc}和{bbb,ddd}连通{bbb,ddd}和{ddd,hhh}连通根据传递性{aaa,bbb,ccc}和{ddd,hhh}也连通。最终它们属于同一个连通分量。这里有个细节传递性只保证“在同一个分量里”不保证“任意两个元素直接相连”。比如aaa和hhh之间并没有直接共享元素但通过bbb和ddd这条路径它们被归到了一起。理解这一点对调试很有帮助——当你发现两个看似无关的元素被合并了顺着路径查一遍通常能找到中间那个“桥梁元素”。3.3 合并顺序会影响中间状态但不影响最终结果有人担心先合并{bbb,ddd}还是先合并{ddd,hhh}会不会导致结果不同答案是最终分组结果不变但中间过程可能不同。这是并查集的一个重要性质——合并操作满足结合律和交换律只要所有该合并的都合并了最终连通分量是唯一的。不过中间状态不同会影响性能。比如按秩合并时总是把矮树挂到高树下能让树高保持在 O(log n)。如果随便挂极端情况下树会退化成链表查询变成 O(n)。所以虽然结果一样实现时还是要讲究策略。3.4 空集和单元素集合的处理输入里{ggg}是单元素集合它没有和任何其他集合共享元素所以单独成组。这里要注意空集{}和单元素集合的处理逻辑不同。空集和任何集合的交集都是空所以它永远不会被合并但它在输出里要不要保留这取决于业务需求。有些场景要求过滤掉空集有些要求保留占位。我在数据清洗时通常会把空集丢掉因为空集不携带任何信息留着只会干扰后续统计。单元素集合则要保留因为它可能代表一个独立的实体。比如{ggg}可能是一个独立用户虽然暂时没有关联标签但不能丢。3.5 重复元素的去重如果输入里出现{aaa,bbb}和{aaa,bbb}两个完全相同的集合合并后应该只剩一个{aaa,bbb}。标准集合运算天然去重但如果你用列表存储元素就要手动去重。我见过有人用list存集合元素合并时直接extend结果输出里aaa出现了两次下游统计全乱套。用set或哈希结构存元素是避免这类问题的第一道防线。4. 实操过程从零实现这套合并运算4.1 方案一反复扫描合并适合小数据量先给一个 Python 版本逻辑最直白适合理解原理。def merge_sets_naive(sets): sets [set(s) for s in sets] changed True while changed: changed False result [] used [False] * len(sets) for i in range(len(sets)): if used[i]: continue current sets[i] used[i] True j i 1 while j len(sets): if not used[j] and current sets[j]: current current | sets[j] used[j] True changed True j i 1 # 重新扫描因为 current 变大了 else: j 1 result.append(current) sets result return sets这段代码的关键在j i 1那一行。每次合并后current变大了必须从头再比一遍否则会漏掉新产生的交集。我第一版写的时候就是忘了这行测试用例{a,b},{c,d},{b,c}直接挂了排查了半小时才反应过来。跑一下输入input_sets [ {aaa,bbb,ccc}, {bbb,ddd}, {eee,fff}, {ggg}, {ddd,hhh} ] print(merge_sets_naive(input_sets)) # 输出: [{aaa,bbb,ccc,ddd,hhh}, {eee,fff}, {ggg}]结果正确。但这个算法的时间复杂度在最坏情况下是 O(n³)集合数量超过几百个就会明显变慢。4.2 方案二并查集实现适合生产环境并查集的 Python 实现带路径压缩和按秩合并class UnionFind: def __init__(self): self.parent {} self.rank {} def add(self, x): if x not in self.parent: self.parent[x] x self.rank[x] 0 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): rx, ry self.find(x), self.find(y) if rx ry: return if self.rank[rx] self.rank[ry]: rx, ry ry, rx self.parent[ry] rx if self.rank[rx] self.rank[ry]: self.rank[rx] 1 def merge_sets_unionfind(sets): uf UnionFind() for s in sets: s list(s) for elem in s: uf.add(elem) for i in range(1, len(s)): uf.union(s[0], s[i]) groups {} for elem in uf.parent: root uf.find(elem) groups.setdefault(root, set()).add(elem) return list(groups.values())跑同样的输入输出一致。但性能上并查集版本处理十万个集合、百万级元素通常也就几秒钟而反复扫描版本早就卡死了。4.3 参数选择与性能对比我做过一组实测环境是普通笔记本Python 3.10数据随机生成元素为字符串集合数量平均集合大小反复扫描耗时并查集耗时10050.02s0.01s100051.8s0.05s5000545s0.3s1000010超时0.8s数据量到 1000 以上差距就非常明显了。所以我的经验是原型验证用反复扫描生产环境一律并查集。不要为了省那几十行代码给自己埋性能雷。4.4 输出格式的整理并查集分完组后groups是一个字典值是set。如果业务要求输出有序结果比如按集合内元素字典序排列或者按集合大小排序需要额外处理result [sorted(g) for g in groups.values()] result.sort(keylambda x: (len(x), x))这个例子里按大小排序后是{ggg}、{eee,fff}、{aaa,bbb,ccc,ddd,hhh}。但题目给的输出顺序是大的在前所以具体排序规则要按需求来不要想当然。4.5 跨语言实现的注意点如果用 JavaHashSet的retainAll可以做交集判断但注意retainAll会修改原集合用之前先拷贝一份。如果用 Cstd::set_intersection需要先排序或者直接用std::unordered_set做哈希判断。如果用 JavaScriptSet没有内置交集方法得自己写循环。不管哪种语言核心逻辑都一样先建映射再 union最后按根分组。语言只是壳思路才是关键。5. 常见问题与排查技巧实录5.1 合并结果少了一组怎么办这是最常见的 bug。表现是明明{a,b}和{b,c}应该合并结果输出里它们还是分开的。排查步骤检查 union 操作是否覆盖了集合内所有元素。有些人只 union 了相邻两个比如{a,b,c}只 union 了a-b和b-c漏了a-c。虽然传递性能补上但如果实现有 buga-c可能没连上。检查 find 是否做了路径压缩。没压缩时树可能退化成链find 返回的根节点不一致导致分组错误。检查是否有元素没被 add 进并查集。如果某个元素只在 union 时出现但没初始化 parentfind 会报错或返回错误结果。注意并查集的add操作必须在union之前完成否则parent字典里没有这个键find直接 KeyError。5.2 输出里出现重复元素原因通常是用了list存元素合并时直接拼接。解决方案全程用set或者在输出前做一次set()转换。我见过更隐蔽的情况元素是自定义对象没有重写__hash__和__eq__导致set认为两个相同对象是不同的元素。这时候要么重写这两个方法要么用唯一 ID 代替对象本身。5.3 性能突然变慢如果并查集版本跑小数据很快大数据突然卡住八成是路径压缩没生效。检查find里有没有这行self.parent[x] self.find(self.parent[x])没有这行树高会随着 union 次数增加而增长find 从 O(1) 退化到 O(n)。另一个可能是按秩合并写反了把高树挂到了矮树下同样会导致树高失控。5.4 元素类型不一致输入里aaa是字符串但实际数据里可能混入数字123和字符串123。在 Python 里123 123是 False但在某些语言里会隐式转换。统一元素类型是合并前的必要步骤。我的做法是全部转成字符串或者全部转成整数避免类型歧义。5.5 常见问题速查表问题现象可能原因解决方法结果少合并合并后未重新扫描加changed标记循环到无变化结果多合并元素粒度太粗检查是否误把不同元素当相同重复元素用 list 存储改用 set 或输出前去重性能差无路径压缩在 find 中加路径压缩报 KeyError未初始化 parentunion 前先 add 所有元素顺序不对未排序输出前按业务规则排序5.6 一个容易被忽略的边界自反性如果输入里有一个集合{aaa,aaa}标准集合会自动去重成{aaa}。但如果你的数据结构没去重union 时aaa和自己 union虽然结果不变但会浪费一次操作。更严重的是如果find(aaa)返回的不是aaa本身说明并查集初始化有问题。自反性是并查集的基本性质find(x) 必须能返回 x 所在树的根且 x 自己 union 自己时不应改变任何状态。6. 从这道题延伸出去合并运算的真实应用场景6.1 数据清洗中的标签归并做用户画像时经常遇到一个用户被打上多个标签标签之间有关联关系。比如{篮球, 运动}、{运动, 健身}、{健身, 瑜伽}最终要合并成{篮球, 运动, 健身, 瑜伽}一个大类。这跟集合合并一模一样只是元素从aaa变成了业务标签。我做过一个项目原始标签有八千多个合并后只剩三百多个大类下游推荐系统的准确率直接涨了一截。6.2 图论中的连通分量无向图里找连通分量标准解法就是并查集。每条边相当于一个二元素集合把所有边 union 完剩下的分组就是连通分量。社交网络里找“朋友圈”、网络拓扑里找“子网”、图像处理里找“连通区域”底层都是这套逻辑。6.3 数据库跨表合并去重热搜词里“跨表合并”出现频率很高。两张表如果有共同字段合并时要去重、要归并本质上也是集合运算。SQL 里的UNION是简单合并去重但如果涉及传递性归并就得用递归 CTE 或者应用层并查集。我处理过一个订单合并需求同一个用户在不同渠道下的订单要归并用的就是并查集思路。6.4 版本控制中的分支合并Git 的分支合并虽然复杂得多但核心思想有相通之处找到共同祖先合并差异解决冲突。集合合并可以看作是“无冲突版本”的简化模型——只要两个集合有交集就自动合并不需要人工介入。理解了这个简化模型再看 Git 的合并策略会更容易抓住本质。6.5 文件分片合并热搜词里“合并多个小分片ts分段视频”“分卷文件怎么合并”也是同类问题。分片文件按序号排列合并时按顺序拼接即可但如果分片之间有重叠或缺失就需要先做集合运算找出完整覆盖。这跟集合合并的“连通性”思路异曲同工。7. 我踩过的坑和几条实用建议第一个坑是过早优化。刚开始写的时候我想着一步到位上并查集结果元素映射、路径压缩、按秩合并一堆细节调试了两小时。后来换成反复扫描版本十分钟就跑通了确认逻辑无误后再替换成并查集反而更快。所以我的建议是先用最笨的方法把逻辑跑通再考虑性能优化。第二个坑是忽略元素顺序。有一次做标签合并产品要求合并后的标签按首次出现顺序排列。我用并查集分完组直接输出set顺序全乱了。后来加了一个OrderedDict记录首次出现位置才满足需求。如果你的业务对顺序敏感一定要在分组后单独排序不要依赖 set 的默认顺序。第三个坑是没有处理空输入。输入为空列表时反复扫描版本直接返回空列表没问题但并查集版本如果没做判空groups字典为空输出也是空看似没问题。但如果下游代码假设输出至少有一个集合就会崩。边界条件测试一定要覆盖空输入、单集合、全无交集、全有交集这四种情况。最后一个建议写单元测试。集合合并的测试用例很好构造随便生成几组数据手动算一遍预期结果跟代码输出对比。我通常至少写五组无交集、全交集、链式交集、环形交集、混合场景。这五组过了基本就不会有逻辑漏洞。这个运算看起来简单但真正写好、写稳、写快还是需要一些经验的。希望这篇能帮你少走点弯路。

集合合并算法详解：从反复扫描到并查集的高效实现

相关推荐

微信小程序点餐系统毕设：源码、数据库设计与避坑指南

上海甲醛检测-18883与50325的标准引用记录实例

深度解析 Claude Code 源码（二）：上下文管理与消息压缩机制

更多资讯

OSM城市知识图谱构建全流程：从数据清洗到Neo4j入库实战

DeepSeek 实战：提示词、本地部署与文档问答全链路

HCIA Datacom H12-811英语版题库备考攻略：从术语到刷题方法

DeepSeek 15天从入门到精通：提问法则、文件处理与知识库搭建实操手册

HW蓝队总结模板：护网行动防守复盘与量化汇报指南

DAY7 CSS184-196

今日更新

PHP htmlentities()函数用法讲解

AI Agent工程实战：从七要素到七个决策点的系统设计指南

AI入局芯片设计验证：验证收敛50倍加速的真相与应对

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？