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，数据随机生成，元素为字符串：
| 集合数量 | 平均集合大小 | 反复扫描耗时 | 并查集耗时 |
|---|---|---|---|
| 100 | 5 | 0.02s | 0.01s |
| 1000 | 5 | 1.8s | 0.05s |
| 5000 | 5 | 45s+ | 0.3s |
| 10000 | 10 | 超时 | 0.8s |
数据量到 1000 以上，差距就非常明显了。所以我的经验是：原型验证用反复扫描，生产环境一律并查集。不要为了省那几十行代码，给自己埋性能雷。
4.4 输出格式的整理
并查集分完组后，groups是一个字典，值是set。如果业务要求输出有序结果，比如按集合内元素字典序排列，或者按集合大小排序，需要额外处理：
result = [sorted(g) for g in groups.values()] result.sort(key=lambda x: (len(x), x))这个例子里，按大小排序后是{ggg}、{eee,fff}、{aaa,bbb,ccc,ddd,hhh}。但题目给的输出顺序是大的在前，所以具体排序规则要按需求来，不要想当然。
4.5 跨语言实现的注意点
如果用 Java，HashSet的retainAll可以做交集判断，但注意retainAll会修改原集合，用之前先拷贝一份。如果用 C++，std::set_intersection需要先排序，或者直接用std::unordered_set做哈希判断。如果用 JavaScript，Set没有内置交集方法，得自己写循环。
不管哪种语言，核心逻辑都一样：先建映射，再 union，最后按根分组。语言只是壳，思路才是关键。
5. 常见问题与排查技巧实录
5.1 合并结果少了一组怎么办
这是最常见的 bug。表现是：明明{a,b}和{b,c}应该合并，结果输出里它们还是分开的。排查步骤：
- 检查 union 操作是否覆盖了集合内所有元素。有些人只 union 了相邻两个，比如
{a,b,c}只 union 了a-b和b-c，漏了a-c。虽然传递性能补上，但如果实现有 bug，a-c可能没连上。 - 检查 find 是否做了路径压缩。没压缩时，树可能退化成链，find 返回的根节点不一致，导致分组错误。
- 检查是否有元素没被 add 进并查集。如果某个元素只在 union 时出现，但没初始化 parent，find 会报错或返回错误结果。
注意：并查集的
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 | 未初始化 parent | union 前先 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字典为空，输出也是空，看似没问题。但如果下游代码假设输出至少有一个集合，就会崩。边界条件测试一定要覆盖空输入、单集合、全无交集、全有交集这四种情况。
最后一个建议：写单元测试。集合合并的测试用例很好构造，随便生成几组数据，手动算一遍预期结果，跟代码输出对比。我通常至少写五组：无交集、全交集、链式交集、环形交集、混合场景。这五组过了，基本就不会有逻辑漏洞。
这个运算看起来简单，但真正写好、写稳、写快，还是需要一些经验的。希望这篇能帮你少走点弯路。
