public List<List<String>> accountsMerge(List<List<String>> accounts) {
List<List<String>> res = new ArrayList<>();
if (accounts == null || accounts.size() == 0) {
Map<String, String> emailToName = new HashMap<>();
Map<String, Set<String>> graph = new HashMap<>();
Set<String> emails = new HashSet<>();
for (List<String> account : accounts) {
String name = account.get(0);
for (int i = 1; i < account.size(); i++) {
String email = account.get(i);
emailToName.put(email, name);
graph.putIfAbsent(email, new HashSet<>());
graph.get(account.get(i - 1)).add(email);
graph.get(email).add(account.get(i - 1));
Set<String> visited = new HashSet<>();
for (String email : emails) {
if (!visited.contains(email)) {
List<String> buffer = new ArrayList<>();
findConnectedComponentByDFS(email, graph, visited, buffer);
Collections.sort(buffer);
buffer.add(0, emailToName.get(email));
public void findConnectedComponentByDFS(String email, Map<String, Set<String>> graph, Set<String> visited, List<String> buffer) {
for (String nextEmail : graph.get(email)) {
if (!visited.contains(nextEmail)) {
findConnectedComponentByDFS(nextEmail, graph, visited, buffer);