721. Accounts Merge

Link

Solution

The hardest part is to figure out building a Graph of the email address and how to do it.

ex: Name, addr1, addr2, addr3, addr4

Name, addr2, addr5, addr6,

Name, addr7, addr8

We will build a graph like below:

addr1: addr2 addr2: addr1, addr3, addr5, addr6 addr3: addr2, addr4, addr4: addr3 addr5: addr2, addr6 addr6: addr5 addr7: addr8 addr8: addr7 Once we have the graph, we will do the DFS to find out all the related addresses. By a visited Map to record the email address is checked, it will be easy to find out which emails address are related.

 public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, HashSet<String>> emailGraph = new HashMap<>();
        Map<String, String> nameMap = new HashMap<>();
        
        //Build Graph (emailGraph is crucial)
        for(List<String> account : accounts){
            String name = account.get(0);
            for(int i = 1; i < account.size(); i++){
                if(!emailGraph.containsKey(account.get(i))){
                    emailGraph.put(account.get(i), new HashSet<String>());
                }
                nameMap.put(account.get(i), name);
                if(i != 1){
                    emailGraph.get(account.get(i)).add(account.get(i-1));
                    emailGraph.get(account.get(i-1)).add(account.get(i));
                }
            }
        }
        
        //DFS
        List<List<String>> ret = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        for(String email : emailGraph.keySet()){
            if(visited.contains(email)) continue;
            List<String> mergedAccount = new LinkedList<>();
            dfs(emailGraph, email, mergedAccount, visited);
            Collections.sort(mergedAccount);
            mergedAccount.add(0, nameMap.get(email));
            ret.add(mergedAccount);
        }
        return ret;
    }
    
    public void dfs(Map<String, HashSet<String>> emailGraph, String email, 
                    List<String> mergedAccount, Set<String> visited){
        
        if(visited.contains(email)) return;
        visited.add(email);
        mergedAccount.add(email);
        Set<String> mails = emailGraph.get(email);
        
        for(String mail : mails){
            dfs(emailGraph, mail, mergedAccount, visited);
        }
    }