class Solution {
	Map<String, List<String>> graph;
    Set<String> seen;
    public List<List<String>> accountsMerge(List<List<String>> accounts) {

        graph = new HashMap<>();
        seen = new HashSet<>();

        buildGraph(accounts);

        Map<String, String> email_to_name = new HashMap<>();
        for (List<String> account:accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size(); ++i) {
                String email = account.get(i);
                email_to_name.put(email, name);
            }
        }

        List<List<String>> ans = new ArrayList<>();
        for (String email:email_to_name.keySet()) {
            if (!seen.contains(email)) {
                List<String> comp = new ArrayList<>();
                dfs(email, comp);
                Collections.sort(comp);
                //System.out.println(comp.size());
                ans.add(new ArrayList());
                ans.get(ans.size()-1).add(email_to_name.get(email));
                ans.get(ans.size()-1).addAll(comp);
            }
        }

        return ans;
    }

    public void buildGraph(List<List<String>> accounts) {
        for (List<String> account:accounts) {
            if (account.size() == 2) {
                graph.computeIfAbsent(account.get(1),
                                      z -> new ArrayList());
                continue;
            }

            for (int i = 1; i < account.size(); ++i)
                for (int j = i+1; j < account.size(); ++j) {
                    graph.computeIfAbsent(account.get(i),
                                         z -> new ArrayList()).add(account.get(j));
                    graph.computeIfAbsent(account.get(j),
                                         z -> new ArrayList()).add(account.get(i));
                }
        }
    }

    public void dfs(String email, List<String> comp) {
        if (seen.contains(email))
            return;
        comp.add(email);
        seen.add(email);

        for (String nei: graph.get(email)) {
            dfs(nei, comp);
        }

    }
}