721. Accounts Merge

本文主要是介绍721. Accounts Merge，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

The most important things to solve this problem are:

1.  recognizing this is a graph problem.
2. Select a correct data structure to store the graph: 

   Map<String, Set<String>> graph = new HashMap<>();

The rest is easy.

DFS+BFS solution:

class Solution {
    Set<String> visited= new HashSet<>();
    
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        List<List<String>> res = new ArrayList<>();
        Map<String, String> emailName = new HashMap<>();
        Map<String, Set<String>> graph = new HashMap<>();
        
        for(List<String> account:accounts){
            String name = account.get(0);
            for(int i=1;i<account.size();i++){
                emailName.put(account.get(i), name);
            }
            for(int i=1;i<account.size();i++){
                graph.putIfAbsent(account.get(i), new HashSet<>());
                for(int j=1;j<account.size();j++){
                    if(i!=j)
                        graph.get(account.get(i)).add(account.get(j));
                }
            }
        }
        Set<String> keys = graph.keySet();
        for(String key: keys){
            if(visited.contains(key))
                continue;
            List<String> list = new ArrayList<>();
            bfs(key, graph, list);
            Collections.sort(list);
            String name = emailName.get(key);
            list.add(0, name);
            res.add(list);
            
        }
        return res;
    }
   
    private void dfs(String key, Map<String, Set<String>> graph, List<String> list){
        if(visited.contains(key))
            return;
        list.add(key);
        visited.add(key);
        Set<String> emails = graph.get(key);
        for(String email:emails){  
            dfs(email, graph, list); 
        }
    }
    
    private void bfs(String key, Map<String, Set<String>> graph, List<String> list){
        Queue<String> queue = new LinkedList<>();
        queue.offer(key);
        visited.add(key);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                String email= queue.poll();
                list.add(email);
                Set<String> neibors = graph.get(email);
                for(String nei:neibors){
                    if(!visited.contains(nei)){
                        queue.offer(nei);
                        visited.add(nei);
                    }
                }
            }
        }
    }
}

这篇关于721. Accounts Merge的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！