题目描述
思路解析动画文字版
记住「邮箱当节点 → 同账户内 union → 按根分组 + 排序 + 冠名」,下面逐帧套它。共享邮箱就是把两个账户连起来的那座桥。
先把所有出现过的邮箱各放一个节点:smith、nyc(john_newyork)、j00(john00)、mary、bravo。此刻它们彼此独立,集合数 = 5,相当于先假设有 5 个互不相干的「人」。
并查集准备就绪:每个邮箱的 parent 先指向自己(自成一集)。接下来按账户顺序扫,遇到同一账户里的邮箱就把它们并起来。
看账户 0(John):它有 smith 和 nyc 两个邮箱。规则是以第一个邮箱 smith 为基准,把后面的邮箱都并到它这一组。
union(smith, nyc):把 smith 的根指到 nyc,两个邮箱连成一条边、归入同一集合(同色)。集合数从 5 降到 4。这俩邮箱确定属于同一个 John。
看账户 1(John):它有 smith 和 j00。注意 smith(标红)之前在账户 0 里出现过,这就是连接两个账户的共享邮箱,说明账户 0 和账户 1 是同一个人!
先对基准邮箱 smith 做 find:smith 的 parent 指向 nyc,顺着走,这一组当前的根是 nyc。找根时顺手做路径压缩,让节点以后更快找到根。
union(smith, j00):把 smith 这一组的根接到 j00 上。于是 smith、nyc、j00 三个邮箱并成同一集合(同色),集合数从 4 降到 3。三个邮箱都归这一个 John。
看账户 2(Mary):只有 mary 一个邮箱。基准就是它自己,union(mary, mary) 等于没动,mary 单独成一集。集合数保持 3。
看账户 3(John):只有 bravo(johnnybravo)一个邮箱。它虽然也叫 John,但和前面那个 John 没有任何共享邮箱。
所以 bravo 不会和前面的 John 合并,它自成一集,这正是本题的坑:同名不代表同一人,要靠共享邮箱判断。四个账户扫完,集合数定格在 3,也就是 3 个不同的人。
四个账户都处理完,看整张图:smith、nyc、j00 三个邮箱连成同一组(一种颜色),mary 自成一色,bravo 自成一色,正好对应面板上的集合数 3。下一步把每一组的邮箱分别收集出来。
分组的办法很直接:对每个邮箱做一次 find 拿到它的根,根相同的就归到同一组里。下面逐个邮箱看。
账户都扫完了,开始分组。对每个邮箱做 find 拿到它的根,根相同的归一组。find(smith) 顺着 smith → … → j00,根是 j00,smith 归到 j00 这组。
find(nyc) 的根也是 j00,nyc 归到同一组。注意路径压缩后,nyc 这些节点会直接挂到根上,下次 find 一步到位。
find(j00) 的根就是 j00 自己。至此 smith、nyc、j00 三个邮箱都归到根 j00 这一组,它们属于同一个 John。
find(mary) 的根是 mary,自己单独一组,属于 Mary。
find(bravo) 的根是 bravo,也单独一组,属于另一个 John。三组分完。
组内排序 + 冠名。j00 这组的邮箱按字典序排成 john00、john_newyork、johnsmith,最前面用 owner 记下的用户名冠上 John → [John, john00, john_newyork, johnsmith]。
Mary 那组只有一个邮箱,排序后就是 [Mary, mary]。
bravo 那组也只有一个,冠上 John → [John, johnnybravo]。和前一个 John 各是各的人。
合并完成:三个人 [John, john00, john_newyork, johnsmith]、[Mary, mary]、[John, johnnybravo]。回头看,我们靠并查集把「共享邮箱 = 同一人」这层关系一边扫一边并起来,集合数 5 → 3 就是答案的人数,既直观又好写。
边界:单邮箱独立;同名不一定合;链式共享会传递合并。
两个追问:DFS/BFS 求连通分量等价;邮箱字符串可直接当并查集的 key。
参考代码
from typing import Listfrom collections import defaultdictclass Solution: def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]: parent = {} owner = {} def find(x): parent.setdefault(x, x) if parent[x] != x: parent[x] = find(parent[x]) return parent[x] def union(a, b): parent[find(a)] = find(b) for acc in accounts: name = acc[0] first = acc[1] for email in acc[1:]: owner[email] = name union(first, email) groups = defaultdict(list) for email in owner: groups[find(email)].append(email) return [[owner[root]] + sorted(emails) for root, emails in groups.items()]复杂度
- 时间：O(E log E)，E 是邮箱总数。并查集的 union/find 近似 O(1)(反阿克曼);最后每组排序合计 O(E log E),由排序主导
- 空间：O(E)，parent、owner、分组表都按邮箱数 E 存,O(E)
易错点
面试追问把动画讲成自己的话
追问能不能不用并查集,改用 DFS/BFS?
追问邮箱是字符串,怎么进并查集?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
网络延迟时间
LeetCode 743 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题