LeetCode 721. 账户合并（Accounts Merge）题解：基于并查集连通分量的经典实战

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", "[e-mail]", "[e-mail]"], ["John", "[e-mail]"], ["John", "[e-mail]", "[e-mail]"], ["Mary", "[e-mail]"] ] Output: [ ["John", "[e-mail]", "[e-mail]", "[e-mail]"], ["John", "[e-mail]"], ["Mary", "[e-mail]"] ] Explanation: 第一个和第三个 John 是同一个人，因为他们有共同的电子邮件 "[e-mail]"。 第二个 John 和 Mary 是不同的人，因为他们的电子邮件地址没有被其他账户使用。

我们可以以任意顺序返回这些列表，例如[["Mary", "[e-mail]"], ["John", "[e-mail]"], ["John", "[e-mail]", "[e-mail]", "[e-mail]"]]仍然会被接受。

数据范围（注意）

• 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()]

代码要点逐行解读

1. UF.__init__：用字典parent存储每个节点的父节点，支持以字符串（邮箱地址）为键，无需预知节点总数。
2. UF.find(x)：setdefault(x, x)保证首次出现的节点以自己为父（自环代表根）；while x != self.parent[x]循环向上找根。注意：这一版没有做路径压缩，树的深度会随合并不断增长。
3. UF.union(p, q)：找到 p、q 各自的根，将 p 的根挂到 q 的根之下，两个邮箱即并入同一连通分量。
4. 主流程：
   • 遍历每个账户，把每个邮箱映射到账户名email_to_name[email] = name；
   • 对同一账户内相邻的两个邮箱执行uf.union(account[i], account[i + 1])，相邻传递即可让整个账户内的邮箱全部连通；
   • 遍历所有邮箱，以uf.find(email)作为 key，把邮箱收集进res（collections.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)$。优化思路有两条：

1. 路径压缩：在find的过程中，把沿途所有节点直接挂到根上，将树高压缩到接近常数，之后继续查找的时间复杂度为 $O(1)$；
2. 按秩合并（小树挂大树）：给每个顶层元素维护一个size表示连通分量大小，union时把小的拼接到大的上，避免树退化成链表。

仓库 thinkings/union-find.md 给出了结合两种优化的完整模板，可直接套用：

class UF: def __init__(self, M): self.parent = {} self.size = {} self.cnt = 0 # 初始化 parent，size 和 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