账户合并问题如何建图？DFS 和并查集分别怎么做？

简化版

账户合并的本质是连通分量：同一个账户里的邮箱属于同一个人，邮箱之间可以连边。最后把所有互相连通的邮箱归为一组，并按字典序输出。可以用 DFS 建邮箱图，也可以用并查集合并邮箱。

详细版

DFS 做法：把每个账户的第一个邮箱作为中心，和该账户中的其他邮箱连边，同时记录邮箱对应的用户名。建完图后，对邮箱图求连通分量，每个分量排序后加上用户名。

并查集做法：把邮箱作为节点，同一账户内的邮箱 union 到一起；最后按根节点分组。并查集更适合“合并关系”表达，DFS 更容易从图连通性角度理解。复杂度主要由邮箱数量和排序决定。

完整版教学

一、为什么账户合并是图问题

题目说如果两个账户共享至少一个邮箱，就属于同一个人。共享邮箱会把不同账户连接起来，连接关系还具有传递性：A 和 B 共享邮箱，B 和 C 共享另一个邮箱，那么 A、B、C 都要合并。

Account1: John a@mail b@mail
Account2: John b@mail c@mail
Account3: Mary x@mail

a -- b -- c   是 John 的连通分量
x             是 Mary 的连通分量

因此真正的节点应是邮箱，而不是账户行。账户行只是告诉我们这一批邮箱之间应该连通。

二、DFS 建图：中心邮箱连边

一个账户里如果有 k 个邮箱，没必要两两连边形成完全图。把第一个邮箱作为中心，连向其余 k-1 个邮箱，就能保证这一账户内所有邮箱连通，边数更少。

账户邮箱数	两两连边	中心连边
3	3 条	2 条
10	45 条	9 条
100	4950 条	99 条

这个优化非常实用。建图时还要记录 email -> name，因为最终输出每组邮箱前面要放用户名。

三、DFS 代码流程

建好邮箱邻接表后，对每个未访问邮箱做 DFS，收集一个连通分量。收集完排序，再把用户名插到最前面。

Map<String, List<String>> graph = new HashMap<>();
Map<String, String> emailToName = new HashMap<>();
for (List<String> acc : accounts) {
    String name = acc.get(0);
    String first = acc.get(1);
    for (int i = 1; i < acc.size(); i++) {
        String email = acc.get(i);
        emailToName.put(email, name);
        graph.putIfAbsent(email, new ArrayList<>());
        graph.putIfAbsent(first, new ArrayList<>());
        graph.get(first).add(email);
        graph.get(email).add(first);
    }
}

DFS 部分就是标准连通分量遍历。注意账户只有一个邮箱时，也要把这个邮箱放进图，否则它可能被漏掉。

四、并查集做法

并查集把同一账户内的邮箱合并到同一个集合。由于邮箱是字符串，通常用 Map<String, String> parent，或者先把邮箱映射成整数编号。

for account in accounts:
  first = account[1]
  for email in account[1..]:
    union(first, email)

for email in allEmails:
  root = find(email)
  group[root].add(email)

如果有 10000 个邮箱，并查集的合并和查找几乎是常数级。最后排序每个分组，排序成本是不可避免的，因为题目要求邮箱按字典序输出。

五、用户名如何处理

经典题默认同一个人的账户名相同，所以分组后用任意一个邮箱对应的名字即可。更稳妥的做法是在读取账户时记录每个邮箱的名字，输出时取分组根邮箱或分组第一个邮箱对应的名字。

emailToName["a@mail"] = "John"
root(a@mail) = b@mail
group[b@mail] = [a@mail, b@mail, c@mail]
output = ["John", "a@mail", "b@mail", "c@mail"]

如果现实业务里同一个邮箱可能绑定不同名字，就需要额外冲突规则；但算法题通常不考这个业务异常。

六、复杂度分析

设总邮箱出现次数为 S，去重后邮箱数为 E。DFS 建图和遍历是 O(S + E) 量级，排序所有分组总成本最坏 O(E log E)。并查集合并是 O(S α(E))，分组和排序同样需要处理所有邮箱。

方法	时间主项	空间	适合表达
DFS 图	建图 + 遍历 + 排序	邻接表较大	连通分量直观
并查集	union/find + 排序	parent map	合并关系清晰

面试时两种都可以，若题目叫“merge”，并查集往往更自然；若想强调图建模，DFS 也很好讲。

七、常见误区与追问

记忆钩子：账户行不是最终节点，邮箱才是节点；共享邮箱把账户串成连通分量。

误区：按账户名合并。 同名不一定同人，必须按共享邮箱合并。
误区：只合并直接共享的两行账户。 共享关系有传递性，要合并整个连通分量。
误区：同一账户内邮箱两两连边。 可以中心连边，连通性相同但边数少很多。
追问：只有一个邮箱的账户怎么处理？ 建图或 parent 初始化时必须加入该邮箱，否则会漏结果。
追问：最终为什么要排序？ 题目通常要求每组邮箱按字典序输出，遍历顺序不能保证有序。
追问：DFS 和并查集怎么选？ DFS 建模直观，并查集更贴近动态合并；复杂度都主要受邮箱数量和排序影响。

八、加强记忆

账户合并的核心不是账户名，而是邮箱连通性。同一账户内邮箱连通，共享邮箱让多个账户连通，最终每个连通分量就是一个合并后的账户。DFS 做法是建邮箱图再找连通分量；并查集做法是 union 同账户邮箱再按根分组。最后别忘了邮箱去重、单邮箱账户和排序输出。

简化版

详细版