LeetCode 721. Accounts Merge

Posted on Edited on In 
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
class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        UF uf = new UF();
        Map<String, Integer> emailToId = new HashMap<>();
        Map<String, String> emailToName = new HashMap<>();
        int id = 0;
        for (List<String> account : accounts) {
            String name = "";
            for (String email : account) {
                if (name.length() == 0) {
                    name = email;
                    continue;
                }
                emailToName.put(email, name);
                if (!emailToId.containsKey(email))
                    emailToId.put(email, id++);
                uf.union(emailToId.get(account.get(1)), emailToId.get(email));
            }
        }
        Map<Integer, List<String>> ans = new HashMap<>();
        for (String email : emailToName.keySet()) {
            int i = uf.find(emailToId.get(email));
            ans.computeIfAbsent(i, k -> new ArrayList<>()).add(email);
        }
        for (List<String> l : ans.values()) {
            Collections.sort(l);
            l.add(0, emailToName.get(l.get(0)));
        }
        return new ArrayList(ans.values());
    }
}
class UF {
    private int[] f;
    public UF() {
        f = new int[10001];
        for (int i = 0; i <= 10000; i++)
            f[i] = i;
    }
    public int find(int i) {
        int j = i;
        while (i != f[i])
            i = f[i];
        while (f[j] != i) {
            int next = f[j];
            f[j] = i;
            j = next;
        }
        return i;
    }
    public void union(int i, int j) {
        f[find(j)] = find(i);
    }
}
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
class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, Set<String>> graph = new HashMap<>();
        Map<String, String> emailToName = new HashMap<>();
        for (List<String> account : accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                graph.computeIfAbsent(account.get(i), k -> new HashSet<>());
                emailToName.put(account.get(i), name);
                if (i == 1) continue;
                graph.get(account.get(i)).add(account.get(i - 1));
                graph.get(account.get(i - 1)).add(account.get(i));
            }
        }
        Set<String> visited = new HashSet<>();
        List<List<String>> ans = new LinkedList<>();
        for (String email : emailToName.keySet()) {
            List<String> list = new LinkedList<>();
            if (visited.add(email)) {
                dfs(graph, email, visited, list);
                Collections.sort(list);
                list.add(0, emailToName.get(email));
                ans.add(list);
            }
        }
        return ans;
    }
    private void dfs(Map<String, Set<String>> graph, String email, Set<String> visited, List<String> list) {
        list.add(email);
        for (String next : graph.get(email))
            if (visited.add(next))
                dfs(graph, next, visited, list);
    }
}