LeetCode 721. 账户合并Accounts Merge题解基于并查集连通分量的经典实战【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文以 LeetCode 721「账户合并Accounts Merge」为切入点讲解如何用并查集Union-Find把「拥有共同邮箱」的多个账户归并为同一个人最终按「姓名 排序后的邮箱列表」输出合并结果。读完本文你将掌握把「等价关系 / 连通性」类问题抽象为并查集的通用建模方法理解find、union两个核心 API 的底层原理并学会用路径压缩与按秩合并把最坏 $O(N)$ 的退化复杂度优化到近乎 $O(1)$。本题收录于本仓库 problems/721.accounts-merge.md与仓库中的并查集专题互相印证。题目描述给定一个列表accounts每个元素accounts[i]是一个字符串列表其中第一个元素accounts[i][0]是名称name其余元素是emails表示该账户的邮箱地址。现在需要合并这些账户如果两个账户拥有至少一个共同的邮箱地址则两个账户必定属于同一个人。请注意即使两个账户具有相同的名称它们也可能属于不同的人同名不同人一个人最初可以拥有任意数量的账户但其所有账户都具有相同的名称。合并账户后按以下格式返回账户每个账户的第一个元素是名称其余元素是按顺序排列的邮箱地址。accounts本身可以以任意顺序返回。示例Input: accounts [ [John, johnsmithmail.com, john00mail.com], [John, johnnybravomail.com], [John, johnsmithmail.com, john_newyorkmail.com], [Mary, marymail.com] ] Output: [ [John, john00mail.com, john_newyorkmail.com, johnsmithmail.com], [John, johnnybravomail.com], [Mary, marymail.com] ] Explanation: 第一个和第三个 John 是同一个人因为他们有共同的电子邮件 johnsmithmail.com。 第二个 John 和 Mary 是不同的人因为他们的电子邮件地址没有被其他账户使用。我们可以以任意顺序返回这些列表例如[[Mary, marymail.com], [John, johnnybravomail.com], [John, john00mail.com, john_newyorkmail.com, johnsmithmail.com]]仍然会被接受。数据范围注意accounts的长度在[1, 1000]范围内accounts[i]的长度在[1, 10]范围内accounts[i][j]的长度在[1, 30]范围内。前置知识并查集Union-Find本题的核心前置知识是并查集。仓库的 thinkings/union-find.md 对该数据结构做了完整讲解并查集是一种树型数据结构用于处理不交集Disjoint Sets的合并及查询问题核心是回答「两个元素是否连通」其基本操作有两个Find确定元素属于哪一个子集返回其所属集合的「代表」/根节点可用于判断两个元素是否属于同一子集Union将两个子集合并成同一个集合。代码上使用parent[x] y表示 x 的父节点是 y通过不断沿parent向上搜索找到根满足parent[x] x的节点即集合代表再比较根是否相同即可判定连通性。并查集只能回答「连通与否」而不能回答「具体的连通路径是什么」本题只需要知道哪些邮箱属于同一个连通分量因此并查集是恰如其分的工具。问题建模把「共同邮箱」抽象成连通关系题目要求合并「有共同邮箱的账户」本质上就是在求连通分量把每个邮箱看作一个节点若两个邮箱出现在同一个账户里就在它们之间连一条边所有通过边互相可达的邮箱构成一个连通分量代表「同一个人」。关键点在于抛开 name 不管只根据 email 建立并查集。同一个accounts[i]中的邮箱彼此连通逐个执行union即可这样最终每个连通分量内的邮箱就属于同一个人再用一个哈希表hashtable记录email - name的映射输出时把连通分量内的邮箱归到对应人名下即可。如果题目不要求输出 name自然根本不需要哈希表做映射——只需要统计/收集连通分量即可。代码实现逐步拆解原文档给出了完整的 Python 解法核心是先实现一个精简的并查集类UF再在Solution.accountsMerge中完成建模与输出class UF: def __init__(self): self.parent {} def find(self, x): self.parent.setdefault(x, x) while x ! self.parent[x]: x self.parent[x] return x def union(self, p, q): self.parent[self.find(p)] self.find(q) class Solution: def accountsMerge(self, accounts: List[List[str]]) - List[List[str]]: uf UF() email_to_name {} res collections.defaultdict(list) for account in accounts: for i in range(1, len(account)): email_to_name[account[i]] account[0] if i len(account) - 1: uf.union(account[i], account[i 1]) for email in email_to_name: res[uf.find(email)].append(email) return [[email_to_name[value[0]]] sorted(value) for value in res.values()]代码要点逐行解读UF.__init__用字典parent存储每个节点的父节点支持以字符串邮箱地址为键无需预知节点总数。UF.find(x)setdefault(x, x)保证首次出现的节点以自己为父自环代表根while x ! self.parent[x]循环向上找根。注意这一版没有做路径压缩树的深度会随合并不断增长。UF.union(p, q)找到 p、q 各自的根将 p 的根挂到 q 的根之下两个邮箱即并入同一连通分量。主流程遍历每个账户把每个邮箱映射到账户名email_to_name[email] name对同一账户内相邻的两个邮箱执行uf.union(account[i], account[i 1])相邻传递即可让整个账户内的邮箱全部连通遍历所有邮箱以uf.find(email)作为 key把邮箱收集进rescollections.defaultdict(list)同一 key 下的邮箱就是同一个人输出时以email_to_name[value[0]]取回姓名再对邮箱列表sorted(value)排序保证结果格式「名称 排序后的邮箱」。为什么按账户内相邻邮箱 union 就够了union具有传递性账户[John, a, b, c]中依次union(a,b)、union(b,c)后a、b、c 三者必在同一连通分量中。因此无需对同一账户内所有邮箱两两 union相邻两两合并即可把复杂度控制在 $O(\text{账户邮箱数})$。复杂度分析设N为邮箱总数节点数M为账户数M ≤ 1000时间复杂度平均 $O(N \log N)$主要来自最终对每个连通分量内邮箱的sorted排序并查集部分平均 $O(\log N)$最坏情况是 $O(N)$——即原文档指出的没有路径压缩时 find/union 会随树高退化空间复杂度使用了parent以及email_to_name、res空间复杂度为 $O(N)$。进阶优化路径压缩与按秩合并原文档明确提示find、union、connected都是典型的模板方法上面的实现没有做路径压缩最差情况下find/union/connected的时间复杂度退化为 $O(N)$。优化思路有两条路径压缩在find的过程中把沿途所有节点直接挂到根上将树高压缩到接近常数之后继续查找的时间复杂度为 $O(1)$按秩合并小树挂大树给每个顶层元素维护一个size表示连通分量大小union时把小的拼接到大的上避免树退化成链表。仓库 thinkings/union-find.md 给出了结合两种优化的完整模板可直接套用class UF: def __init__(self, M): self.parent {} self.size {} self.cnt 0 # 初始化 parentsize 和 cnt # size 是一个哈希表记录每一个联通域的大小其中 key 是联通域的根value 是联通域的大小 # cnt 是整数表示一共有多少个联通域 for i in range(M): self.parent[i] i self.cnt 1 self.size[i] 1 def find(self, x): if x ! self.parent[x]: self.parent[x] self.find(self.parent[x]) # 路径压缩 return self.parent[x] return x def union(self, p, q): if self.connected(p, q): return # 小的树挂到大的树上使树尽量平衡按秩合并 leader_p self.find(p) leader_q self.find(q) if self.size[leader_p] self.size[leader_q]: self.parent[leader_p] leader_q self.size[leader_q] self.size[leader_p] else: self.parent[leader_q] leader_p self.size[leader_p] self.size[leader_q] self.cnt - 1 def connected(self, p, q): return self.find(p) self.find(q)将上述模板的初始化部分改为「遇到新邮箱时setdefault动态建节点」即可无缝替换本题中的精简版UF。在路径压缩 按秩合并双重优化下单次操作的时间复杂度可趋近 $O(1)$更严谨地说是阿克曼函数某个反函数级别的复杂度。举一反三连通性题目的统一解法本题在仓库的并查集专题中被列为「模板题」其核心结论是只要题目出现「连通」「等价」「合并同类项」等关系就可以优先考虑并查集。仓库内还有一系列同源题目可以对照练习547. 省份数量朋友圈求连通分量个数直接统计cnt即可839. 相似字符串组以字符串相似关系建边求连通分量947. 移除最多的同行或同列石头把「同行/同列」抽象为等价关系959. 由斜杠划分区域将网格细分为小块后用并查集数区域1697. 检查边长度限制的路径是否存在离线 并查集的进阶应用3108. 带权图中最小代价行走并查集与位运算结合的变体。它们与 721 的共同点是把问题转化为图上的连通性判定/连通分量统计再套用并查集模板。掌握模板之后这类题目可以快速、低错误率地解决。总结「账户合并」是一道典型的并查集应用题解题路径可以归纳为三步① 把邮箱当作节点、同一账户内的邮箱两两连通② 用并查集求出所有连通分量③ 用哈希表回填姓名并按序输出。在此基础上务必重视路径压缩与按秩合并两种优化避免树高退化导致复杂度劣化到 $O(N)$。完整源码与讲解见 problems/721.accounts-merge.md并查集的理论细节与模板见 thinkings/union-find.md。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考