721.Accounts Merge

-

https://leetcode.com/problems/accounts-merge/discuss/109157

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> emailToName = new HashMap<>();
        Map<String, String> emailToEmail = new HashMap<>();
        Map<String, Set<String>> rootToEmailList = new HashMap<>();

        for(int i = 0; i < accounts.size(); i++){
            List<String> curList = accounts.get(i);
            String name = curList.get(0);
            for(int j = 1; j < curList.size(); j++){
                String email = curList.get(j);
                emailToName.put(email, name);
                emailToEmail.put(email, email);
            }
        }

        for(int i = 0; i < accounts.size(); i++){
            List<String> curList = accounts.get(i);
            String rootMail = find(emailToEmail, curList.get(1));
            for(int j = 2; j < curList.size(); j++){
                String email = curList.get(j);
                String currentRoot = find(emailToEmail, email);
                emailToEmail.put(currentRoot, rootMail);
            }
        }
        for(int i = 0; i < accounts.size(); i++){
            List<String> curList = accounts.get(i);
            String rootMail = find(emailToEmail, curList.get(1));
            if(!rootToEmailList.containsKey(rootMail))
                rootToEmailList.put(rootMail, new HashSet());
            for(int j = 1; j < curList.size(); j++){
                String email = curList.get(j);
                rootToEmailList.get(rootMail).add(email);
            }
        }
        List<List<String>> ans = new ArrayList<>();
        for(String rootMail : rootToEmailList.keySet()){
            List<String> emails = new ArrayList<>(rootToEmailList.get(rootMail));
            Collections.sort(emails);
            emails.add(0, emailToName.get(rootMail));
            ans.add(emails);
        }
        return ans;
    }

    public String find(Map<String, String> emailToEmail, String email){
        if(emailToEmail.get(email).equals(email))
            return email;
        else{
            return find(emailToEmail, emailToEmail.get(email));
        }
    }
}