721. Accounts Merge

这个题解法感觉对图的理解很深刻。一开始先不管name, 只处理emails. 把出现在同一个account里面的email都跟该account的第一个email连接，连接的含义是双向的，就是说把彼此存入到自己的neighbors中，本解法里就是map里对应的HashSet<Strings>. 然后用一个visited来保存访问过的email. 遍历account, 每次取出第一个email, 先检查是不是visited, 因为它可能在别的account里不是第一个email而被访问过，如果是的话我们继续访问就会出现重复结果，因为email最后都会被merge到一个账号。如果没有访问过，我们就要做一个bfs, 从该email出发，找它的所有邻居，加到list里。最后要记得sort所有的emails.最后的最后才把名字加到最前面，构成一组答案。为什么从account的第一个email出发做BFS可以找到所有图中于这个email相连的emails呢？因为在该account中不用说，我们建图的时候就连接了所有的emails to 第一个email，那么我们宽搜很快就能得到这些同一个account的email. 同时，这个email可能出现在其他account的非首个email的位置上，而我们建图的时候，连接了它跟这个account的首个email，那么我们把这个首个email放进queue里面之后，一定能访问到所有跟它连接的在该account里的emails, 所以这个account里的所有emails也可以访问到。因此我们从这个account的第一个email出发做宽搜，一定是找得到所有跟它相连的emails的。

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        List<List<String>> res = new ArrayList<>();
        Map<String, Set<String>> map = new HashMap<>();
        for (List<String> account : accounts){
            for (int i = 1; i < account.size(); i++){
                if (!map.containsKey(account.get(i))){
                    map.put(account.get(i), new HashSet<String>());
                }    
                map.get(account.get(i)).add(account.get(1));
                map.get(account.get(1)).add(account.get(i));
            }
        }
        Set<String> visited = new HashSet<>();
        for (List<String> account : accounts){
            if (!visited.contains(account.get(1))){
                List<String> list = new ArrayList<>();
                bfs(map, account.get(1), visited, list);
                Collections.sort(list);
                list.add(0, account.get(0));
                res.add(list);
            }
        }
        return res;
    }
    
    private void bfs(Map<String, Set<String>> map, String s, Set<String> visited, List<String> list){
        Queue<String> queue = new LinkedList<>();
        queue.offer(s);
        visited.add(s);
        while (!queue.isEmpty()){
            String curt = queue.poll();
            list.add(curt);
            for (String nei : map.get(curt)){
                if (!visited.contains(nei)){
                    queue.offer(nei);
                    visited.add(nei);
                }
            }
        }
    }
}