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;
}
}