账户合并 图解题解

这道题到底在问什么

输入

John[johnsmith, john_newyork] / John[johnsmith, john00] / Mary[mary] / John[johnnybravo]

输出

[John, john00, john_newyork, johnsmith] / [Mary, mary] / [John, johnnybravo]

最优解：一步一步想明白

1. 3记住「邮箱当节点 → 同账户内 union → 按根分组 + 排序 + 冠名」,下面逐帧套它。共享邮箱就是把两个账户连起来的那座桥。
2. 4先把所有出现过的邮箱各放一个节点:smith、nyc(john_newyork)、j00(john00)、mary、bravo。此刻它们彼此独立,集合数 = 5,相当于先假设有 5 个互不相干的「人」。
3. 5并查集准备就绪:每个邮箱的 parent 先指向自己(自成一集)。接下来按账户顺序扫,遇到同一账户里的邮箱就把它们并起来。
4. 6看账户 0(John):它有 smith 和 nyc 两个邮箱。规则是以第一个邮箱 smith 为基准,把后面的邮箱都并到它这一组。
5. 7union(smith, nyc):把 smith 的根指到 nyc,两个邮箱连成一条边、归入同一集合(同色)。集合数从 5 降到 4。这俩邮箱确定属于同一个 John。
6. 8看账户 1(John):它有 smith 和 j00。注意 smith(标红)之前在账户 0 里出现过,这就是连接两个账户的共享邮箱,说明账户 0 和账户 1 是同一个人!
7. 9先对基准邮箱 smith 做 find:smith 的 parent 指向 nyc,顺着走,这一组当前的根是 nyc。找根时顺手做路径压缩,让节点以后更快找到根。
8. 10union(smith, j00):把 smith 这一组的根接到 j00 上。于是 smith、nyc、j00 三个邮箱并成同一集合(同色),集合数从 4 降到 3。三个邮箱都归这一个 John。
9. 11看账户 2(Mary):只有 mary 一个邮箱。基准就是它自己,union(mary, mary) 等于没动,mary 单独成一集。集合数保持 3。
10. 12看账户 3(John):只有 bravo(johnnybravo)一个邮箱。它虽然也叫 John,但和前面那个 John 没有任何共享邮箱。
11. 13所以 bravo 不会和前面的 John 合并,它自成一集,这正是本题的坑:同名不代表同一人,要靠共享邮箱判断。四个账户扫完,集合数定格在 3,也就是 3 个不同的人。
12. 14四个账户都处理完,看整张图:smith、nyc、j00 三个邮箱连成同一组(一种颜色),mary 自成一色,bravo 自成一色,正好对应面板上的集合数 3。下一步把每一组的邮箱分别收集出来。
13. 15分组的办法很直接:对每个邮箱做一次 find 拿到它的根,根相同的就归到同一组里。下面逐个邮箱看。
14. 16账户都扫完了,开始分组。对每个邮箱做 find 拿到它的根,根相同的归一组。find(smith) 顺着 smith → … → j00,根是 j00,smith 归到 j00 这组。
15. 17find(nyc) 的根也是 j00,nyc 归到同一组。注意路径压缩后,nyc 这些节点会直接挂到根上,下次 find 一步到位。
16. 18find(j00) 的根就是 j00 自己。至此 smith、nyc、j00 三个邮箱都归到根 j00 这一组,它们属于同一个 John。
17. 19find(mary) 的根是 mary,自己单独一组,属于 Mary。
18. 20find(bravo) 的根是 bravo,也单独一组,属于另一个 John。三组分完。
19. 21组内排序 + 冠名。j00 这组的邮箱按字典序排成 john00、john_newyork、johnsmith,最前面用 owner 记下的用户名冠上 John → [John, john00, john_newyork, johnsmith]。
20. 22Mary 那组只有一个邮箱,排序后就是 [Mary, mary]。
21. 23bravo 那组也只有一个,冠上 John → [John, johnnybravo]。和前一个 John 各是各的人。
22. 24合并完成:三个人 [John, john00, john_newyork, johnsmith]、[Mary, mary]、[John, johnnybravo]。回头看,我们靠并查集把「共享邮箱 = 同一人」这层关系一边扫一边并起来,集合数 5 → 3 就是答案的人数,既直观又好写。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from collections import defaultdict
class 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()]

#include <algorithm>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
    unordered_map<string,string> parent;
    string find(const string& x) {
        if (!parent.count(x)) parent[x] = x;
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        parent.clear();
        unordered_map<string,string> owner;
        for (auto &acc : accounts) {
            string first = acc[1];
            for (int i = 1; i < (int)acc.size(); ++i) {
                owner[acc[i]] = acc[0];
                parent[find(first)] = find(acc[i]);
            }
        }
        unordered_map<string, vector<string>> groups;
        for (auto &[email, name] : owner) groups[find(email)].push_back(email);
        vector<vector<string>> ans;
        for (auto &[root, emails] : groups) {
            sort(emails.begin(), emails.end());
            vector<string> row{owner[root]};
            row.insert(row.end(), emails.begin(), emails.end());
            ans.push_back(row);
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    Map<String, String> parent = new HashMap<>();
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        parent.clear();
        Map<String, String> owner = new HashMap<>();
        for (List<String> acc : accounts) {
            String first = acc.get(1);
            for (int i = 1; i < acc.size(); i++) {
                owner.put(acc.get(i), acc.get(0));
                parent.put(find(first), find(acc.get(i)));
            }
        }
        Map<String, List<String>> groups = new HashMap<>();
        for (String email : owner.keySet()) groups.computeIfAbsent(find(email), k -> new ArrayList<>()).add(email);
        List<List<String>> ans = new ArrayList<>();
        for (Map.Entry<String, List<String>> e : groups.entrySet()) {
            Collections.sort(e.getValue());
            ArrayList<String> row = new ArrayList<>();
            row.add(owner.get(e.getKey()));
            row.addAll(e.getValue());
            ans.add(row);
        }
        return ans;
    }
    private String find(String x) {
        parent.putIfAbsent(x, x);
        if (!parent.get(x).equals(x)) parent.put(x, find(parent.get(x)));
        return parent.get(x);
    }
}

复杂度

面试官可能追问