1、前言

2、思路

这道题关键是构建图，一般用第一个邮箱作为关键节点构建图，其余节点与第一个节点链接，共同构建连通图。然后对每一个进行遍历，将邮箱加入即可。

3、代码

class Solution {
    class Graph{
        String val;
        List<Graph> neighbors = new ArrayList<>();

        public Graph(String val){
            this.val = val;
        }
    }

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, Graph> map = new HashMap<>();
        for (List<String> account : accounts) {
            String master = account.get(1);
            Graph node = map.getOrDefault(master, new Graph(master));
            map.put(master, node);
            for(int i = 2; i < account.size(); i++){
                String email = account.get(i);
                // 用 master 连剩下的邮箱
                Graph otherNode = map.getOrDefault(email, new Graph(email));
                node.neighbors.add(otherNode);
                

                // 此处只是为了让所有邮箱成为连通图
                otherNode.neighbors.add(node);
                map.put(email, otherNode);
            }
        }

        List<List<String>> res = new ArrayList<>();
        Set<String> visited = new HashSet<>();
        for (List<String> account : accounts) {
            List<String> emails = new LinkedList<>();
            String master = account.get(1);

            dfs(visited, emails, map.get(master), master);
            if(emails.size() != 0){
                emails.sort(((o1, o2) -> o1.compareTo(o2)));
                emails.add(0, account.get(0));
                res.add(emails);
            }
        }

        return res;
    }


    private void dfs(Set<String> visited, List<String> emails, Graph node, String master){
        if(visited.contains(master)){
            return;
        }

        emails.add(master);
        visited.add(master);

        for (Graph neighbor : node.neighbors) {
            dfs(visited, emails, neighbor, neighbor.val);
        }
    }
}