GraphAccountMerge - 圖論帳戶合併深度解析與企業應用

1
2
3
4
5
6
7
8

輸入：
[["John","john@mail","john_r@mail"],
 ["John","johnr@mail","john@mail"],   ← 與第一個共用 john@mail
 ["Mary","mary@mail"]]

輸出：
[["John","john@mail","john_r@mail","johnr@mail"],
 ["Mary","mary@mail"]]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> parent = new HashMap<>();  // email -> root email
        Map<String, String> owner = new HashMap<>();   // email -> name

        // 初始化：每個 email 的 parent 是自己
        for (List<String> account : accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                parent.putIfAbsent(account.get(i), account.get(i));
                owner.put(account.get(i), name);
            }
        }

        // Union：同一帳號內的所有 email union 到第一個 email
        for (List<String> account : accounts) {
            String first = account.get(1);
            for (int i = 2; i < account.size(); i++) {
                union(parent, first, account.get(i));
            }
        }

        // 分組：用 root email 作 key 收集所有同組 email
        Map<String, TreeSet<String>> groups = new HashMap<>();
        for (String email : parent.keySet()) {
            String root = find(parent, email);
            groups.computeIfAbsent(root, k -> new TreeSet<>()).add(email);
        }

        // 組裝結果
        List<List<String>> result = new ArrayList<>();
        for (Map.Entry<String, TreeSet<String>> entry : groups.entrySet()) {
            List<String> merged = new ArrayList<>();
            merged.add(owner.get(entry.getKey()));  // 加姓名
            merged.addAll(entry.getValue());         // emails 已 TreeSet 排序
            result.add(merged);
        }
        return result;
    }

    private String find(Map<String, String> parent, String x) {
        if (!parent.get(x).equals(x)) {
            parent.put(x, find(parent, parent.get(x)));  // path compression
        }
        return parent.get(x);
    }

    private void union(Map<String, String> parent, String x, String y) {
        String rx = find(parent, x);
        String ry = find(parent, y);
        if (!rx.equals(ry)) {
            parent.put(rx, ry);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// DFS 解法（概念）
Map<String, List<String>> graph = new HashMap<>();
Map<String, String> emailToName = new HashMap<>();

// 建圖
for (List<String> account : accounts) {
    String name = account.get(0);
    String first = account.get(1);
    emailToName.put(first, name);
    for (int i = 1; i < account.size(); i++) {
        emailToName.put(account.get(i), name);
        graph.computeIfAbsent(first, k -> new ArrayList<>()).add(account.get(i));
        graph.computeIfAbsent(account.get(i), k -> new ArrayList<>()).add(first);
    }
}

// DFS 找連通分量
Set<String> visited = new HashSet<>();
List<List<String>> result = new ArrayList<>();
for (String email : graph.keySet()) {
    if (!visited.contains(email)) {
        List<String> component = new ArrayList<>();
        dfs(graph, visited, component, email);
        Collections.sort(component);
        component.add(0, emailToName.get(email));
        result.add(component);
    }
}