LeetCode 721. Accounts Merge 并查集解法详解：用 Go 合并同一用户的邮箱账户

LeetCode 721. Accounts Merge 并查集解法详解：用 Go 合并同一用户的邮箱账户

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本文围绕 LeetCode 721 题《Accounts Merge（账户合并）》展开，以本仓库 LeetCode-Go 中 leetcode/0721.Accounts-Merge/README.md 为骨架，结合 721. Accounts Merge.go 的两套完整实现与 721. Accounts Merge_test.go 的测试用例，系统讲解「如何通过邮箱关联判定同一人、并用并查集（Union-Find）高效合并账户」的核心算法。读完本文，你将掌握并查集在字符串关联场景下的编号建模方法、两种实现方案的取舍，以及排序去重等边界坑点的处理技巧，可直接迁移到图连通分量、好友推荐等同类问题中。

一、题目理解：如何判定两个账户属于同一个人

题目给定一个列表accounts，其中每个元素accounts[i]是一个字符串列表：第一个元素是姓名（name），其余元素是该账户下的邮箱（emails）。

合并规则只有一条：

如果两个账户存在任意一个相同的邮箱，则这两个账户必定属于同一个人。

题目同时强调两个容易忽略的前提：

1. 同名不一定是同一人：不同人可以有相同名字，例如示例中的第二个 "John" 与第一、三个 "John" 只是恰好同名。
2. 同一人的所有账户必然同名：一个人可以拥有多个账户，但这些账户的名称一定相同，因此合并后的结果里姓名不会冲突。

输出格式要求：每个合并后的账户，第一个元素是姓名，其余元素是邮箱，且邮箱必须按字典序排序；合并结果本身可以以任意顺序返回。

输入约束

示例分析

输入: accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]] 输出: [["John", "john00@mail.com", "john_newyork@mail.com", "johnsmith@mail.com"], ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]

• 第 1 个和第 3 个 "John" 共享邮箱johnsmith@mail.com，判定为同一人，合并成一个账户；
• 第 2 个 "John" 的邮箱johnnybravo@mail.com未出现在其他账户中，虽然是同名，但属于另一个人，保持独立；
• "Mary" 同理，独立成账户；
• 合并后的邮箱john00@mail.com、john_newyork@mail.com、johnsmith@mail.com已按字典序排序。

二、解题思路：为什么选用并查集

从问题模型看，账户是节点、共享的邮箱是连接账户的边，合并的本质就是求连通分量——这正是并查集（Union-Find / Disjoint Set Union）的经典应用场景。

但直接对账户两两暴力比对邮箱是否相交，时间复杂度是O(n² · m²)（n为账户数，m为每账户邮箱数），在最坏情况n = 1000时难以接受。文档给出的优化方向是：

先把每组数据都进行编号：人编号、每个邮箱都编号，映射关系用map记录；再利用并查集的union()操作把这些编号合并；最后把人的编号和对应邮箱的编号拼接起来。

也就是说，不需要预先知道哪些账户是一伙的——只要两个账户出现过同一个邮箱，在遍历邮箱时它们就会被union()到同一个集合里，连通性完全由邮箱的共享关系自动建立。

仓库中还沉淀了一套通用的并查集模板 template/UnionFind.go，本题两种解法均复用了它：

// 路径压缩 + 秩优化 type UnionFind struct { parent, rank []int count int }

Init(n)负责初始化n个独立集合；Find(p)在查找根节点的同时进行路径压缩；Union(p, q)按**秩（rank）**合并两棵子树，保证树高接近对数级；TotalCount()返回当前连通分量个数。这套模板让题解代码聚焦于业务建模，而非重复造轮子。

三、解法一：并查集 + 邮箱编号映射（推荐，O(n·m·α)）

完整实现见 721. Accounts Merge.go 中的accountsMerge函数。整体分三步：

第一步：初始化并查集并扫描邮箱，建立映射

uf := template.UnionFind{} uf.Init(len(accounts)) // 以账户下标作为「人」的编号 emailToID, idToName, idToEmails, res := make(map[string]int), make(map[int]string), make(map[int][]string), [][]string{} for id, acc := range accounts { idToName[id] = acc[0] // 记录每个账户下标对应的姓名 for i := 1; i < len(acc); i++ { pid, ok := emailToID[acc[i]] if ok { uf.Union(id, pid) // 该邮箱之前出现过，说明当前账户与之前账户是同一人 } emailToID[acc[i]] = id // 记录邮箱最后一次归属的账户编号 } }

关键设计：emailToID以邮箱为键、账户下标为值。扫描过程中一旦发现某个邮箱已经被某个账户占用，就把当前账户id与那个账户pid做Union，从而把整个「共享邮箱链」上的账户逐步并入同一集合。这个技巧把邮箱的共享关系转化为并查集边，一步到位。

第二步：按根节点汇聚邮箱

for email, id := range emailToID { pid := uf.Find(id) // 找到该邮箱所属账户的根 idToEmails[pid] = append(idToEmails[pid], email) }

每个邮箱只出现一次（map 天然去重），通过Find(id)找到它所在连通分量的代表账户pid，再把邮箱挂到pid名下。同一个人的所有邮箱因为属于同一个连通分量，会自动汇聚到同一个代表账户下。

第三步：按姓名 + 排序邮箱组装结果

for id, emails := range idToEmails { name := idToName[id] sort.Strings(emails) // 邮箱字典序排序 res = append(res, append([]string{name}, emails...)) } return res

把代表账户的姓名取出，与排序后的邮箱拼装成[]string输出。因为idToEmails的 key 是并查集根节点，同一连通分量只会输出一次，不会产生重复账户。

复杂度分析

设账户数为n，每个账户邮箱数至多为m（本题m ≤ 9）。在路径压缩 + 秩优化的并查集下，单次Find/Union的均摊复杂度为反阿克曼函数α(n)，可视为常数：

• 时间复杂度：O(n·m·α(n))，其中扫描建图与按邮箱归并各为O(n·m·α(n))，最终排序累计O(n·m·log m)；
• 空间复杂度：O(n·m)，用于存储emailToID、idToName、idToEmails三张映射表。

相比暴力两两比对O(n²·m²)，该解法在账户数量大时优势显著。

四、解法二：并查集 + 两两暴力比对（教学对照）

同一文件中的accountsMerge1提供了另一套思路，适合作为对照理解并查集的边界，但不推荐在生产场景使用：

uf, res, visited := template.UnionFind{}, [][]string{}, map[int]bool{} uf.Init(len(accounts)) for i := 0; i < len(accounts); i++ { for j := i + 1; j < len(accounts); j++ { if accounts[i][0] == accounts[j][0] { // 仅同名才可能合并 tmpA, tmpB, flag := accounts[i][1:], accounts[j][1:], false for j := 0; j < len(tmpA); j++ { // 双重循环比对邮箱 for k := 0; k < len(tmpB); k++ { if tmpA[j] == tmpB[k] { flag = true; break } } if flag { break } } if flag { uf.Union(i, j) } } } }

该解法先做O(n²)级别的两两账户邮箱交集判定（只有姓名相同才可能属于同一人），命中共享邮箱后执行Union；随后用visited标记已归并账户，借助临时map完成邮箱去重、sort.Strings排序后输出。虽然逻辑直观，但时间复杂度为O(n²·m²)，当n接近 1000 时明显退化——这正是解法一用「邮箱编号 + map 索引」替代「两两比对」的意义所在。

五、两个易踩的坑：未合并账户也要排序去重

文档明确指出本题有 2 处边界容易出错：

1. 不需要合并的用户邮箱列表也要排序：即使某个账户从未与任何账户共享邮箱（如示例中的johnnybravo@mail.com），它的邮箱依然要按字典序输出；
2. 同一人的所有邮箱要全部汇聚并去重：同一账户内部可能出现重复邮箱，合并后的账户内部不能有重复项。

这两点在测试用例中均有体现，见 721. Accounts Merge_test.go：

• 第 2 组用例中，Ethan账户内出现了重复的Ethan3@m.co，期望输出只保留一个；
• 第 3 组用例中，5 个同名 "David" 账户通过邮箱两两交织最终全部合并为一个账户，且 6 个邮箱严格排序去重。

解法一之所以天然规避这两个坑：emailToID以邮箱为键，重复邮箱只会被索引一次（去重）；归并后再统一sort.Strings（排序），无论是否发生合并都成立。解法二则依赖tmpMap手动去重 +sort.Strings排序，逻辑上需格外小心遗漏。

六、测试验证：覆盖率 100% 的用例设计

本仓库的测试命令统一由 gotest.sh 驱动：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

对本题单独运行：

go test ./leetcode/0721.Accounts-Merge/ -v -run Test_Problem721 -count=1

721. Accounts Merge_test.go 中Test_Problem721覆盖了 4 组典型场景：

且测试同时调用accountsMerge与accountsMerge1两种实现，确保两套解法输出一致。这 4 组用例与文档「题目也提到了这些点，只能归自己没注意这些边界情况」的告诫一一对应，可作为你自行编写测试时的参考模板。

七、总结：从本题到并查集通用建模

LeetCode 721 的核心价值在于演示了并查集的「编号建模」思想：当待合并的元素不是天然的数字索引（而是姓名、邮箱等字符串）时，先用map为每个实体分配唯一编号，再基于编号执行Union/Find，最后把集合还原为实体结果。这种「字符串 → 编号 → 集合 → 实体」的四步套路，同样适用于好友推荐、连通网络划分、冗余连接检测（如本仓库 0684.Redundant-Connection）等一批图论题。

落实到本题的 Go 实现要点：

• 建模：账户下标即「人」编号，邮箱 → 账户下标存入emailToID；
• 合并：扫描到已存在的邮箱即Union，共享关系自动建边；
• 归并：遍历邮箱 map，按Find根节点汇聚，map 天然去重；
• 输出：sort.Strings排序邮箱，append([]string{name}, emails...)组装结果；
• 复用：直接使用仓库模板 template/UnionFind.go 的路径压缩 + 秩优化实现，保证近似线性的整体复杂度。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go