[Leetcode] Accounts Merge

Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Solution 1:

Find the connected components in the graph

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> emailToName = new HashMap();
        Map<String, ArrayList<String>> graph = new HashMap();
        for (List<String> account: accounts) {
            String name = "";
            for (String email: account) {

                // the first word is the email
                if (name == "") {
                    name = email;
                    continue;
                }

                // every email is getting connected with an edge to the first email in that list
                graph.computeIfAbsent(email, x-> new ArrayList<String>()).add(account.get(1));

                // the first email is also getting connected by an edge to all the other emails in the list
                graph.computeIfAbsent(account.get(1), x-> new ArrayList<String>()).add(email);
                emailToName.put(email, name);
            }
        }

        Set<String> seen = new HashSet();
        List<List<String>> ans = new ArrayList();
        for (String email: graph.keySet()) {
            if (!seen.contains(email)) {
                seen.add(email);
                Stack<String> stack = new Stack();
                stack.push(email);
                List<String> connectedComponent = new ArrayList();
                while (!stack.empty()) {

                    // once all the nodes in a connectedComponent are looked at, the stack becomes empty
                    String node = stack.pop();
                    connectedComponent.add(node);
                    for (String nei: graph.get(node)) {
                        if (!seen.contains(nei)) {
                            seen.add(nei);
                            stack.push(nei);
                        }
                    }
                }
                Collections.sort(connectedComponent);
                connectedComponent.add(0, emailToName.get(email));

                // add the name to the first element in the connectedComponents list
                ans.add(connectedComponent);
            }
        }
        return ans;
    }
}