Account Merge

AccountMerge.java

public List<List<String>> accountsMerge(List<List<String>> accounts) {
    if (accounts == null || accounts.size() == 0) {
        return new ArrayList<>();
    }
    UnionFind uf = new UnionFind(10000);
    Map<String, String> emailName  = new HashMap<>();
    Map<String, Integer> emailId = new HashMap<>();
    Map<Integer, List<String>> tempRes = new HashMap<>();
    int index = 0;

    for (List<String> account : accounts) {
        String name = account.get(0);
        for (int i = 1; i < account.size(); i++) {
            // 要检测没有加过，不然会重复加相同email，到不同id
            if (!emailId.containsKey(account.get(i))) {
                emailName.put(account.get(i), name);
                emailId.put(account.get(i), index++);
            }
            // ID 搞错了，还是直接从emailId里面找
            if (i != 1) {  // union with previous email
                uf.union(emailId.get(account.get(1)), emailId.get(account.get(i)));
            }
        }
    }

    for (Map.Entry<String, Integer> entry : emailId.entrySet()) {
        int id = entry.getValue();
        int root = uf.root(id);

        if (!tempRes.containsKey(root)) {
            tempRes.put(root, new ArrayList<>());
        }
        tempRes.get(root).add(entry.getKey());
    }

    List<List<String>> res = new ArrayList<>();
    for (List<String> value : tempRes.values()) {
        /*
        for (int i = 0; i < value.size(); i++) {
            System.out.print(value.get(i) + " ");
        }
        System.out.println();
        */

        // Tweak for this OJ
        Collections.sort(value);

        String name = emailName.get(value.get(0));
        value.add(0, name);
        res.add(value);
    }

    return res;
}