Accounts Merge

graph[first_email].append(email)

Add an edge from the first email to the current email in the graph.

Connecting the first email to all others in the account creates edges that link emails belonging to the same user.

graph[email].append(first_email)

Add an edge from the current email back to the first email to maintain an undirected graph.

Adding edges in both directions ensures the graph is undirected, which is necessary for correct DFS traversal of connected components.

visited.add(email)

Mark the current email as visited.

Marking emails as visited before recursion prevents cycles and duplicate visits, ensuring correctness and efficiency.

dfs(neighbor, component_emails)

Recursively call DFS on the unvisited neighbor email.

Recursion explores the full connected component by visiting all reachable emails.

dfs(email, component_emails)

Perform DFS starting from the current unvisited email to collect connected emails.

This call discovers all emails connected to the starting email, representing one merged account.

graph = defaultdict(list)

Initialize a graph as a default dictionary of lists to store email connections.

This data structure efficiently represents the undirected graph where each email maps to its connected emails, enabling quick adjacency lookups.

visited = set()

Initialize a set to track visited emails during DFS.

The visited set prevents revisiting emails, avoiding infinite loops and redundant processing during DFS.

def dfs(email, component_emails):

Define a recursive DFS function to explore connected emails.

DFS is the core traversal method to find all emails connected to a given email, representing one merged account.

if neighbor not in visited:

Check if the neighbor email has not been visited.

Visiting only unvisited neighbors prevents infinite recursion and redundant work.

if email not in visited:

Check if the current email has not been visited.

Starting DFS only from unvisited emails avoids redundant traversals of already processed components.

res.append([email_to_name[email]] + sorted(component_emails))

Append the merged account to the result list with the name and sorted emails.

Sorting emails and prepending the name formats the merged account correctly for output, fulfilling problem requirements.

email_to_name = {}

Initialize a dictionary to map each email to its account name.

Mapping emails to names allows retrieval of the correct user name after grouping emails, which is essential for constructing the final merged accounts.

first_email = account[1]

Identify the first email in the account to serve as a connection hub.

Using the first email as a hub simplifies graph construction by connecting all other emails in the account to it, ensuring connectivity.

email_to_name[email] = name

Map the current email to the account name.

This ensures that every email can be traced back to the correct user name for final output.

component_emails.append(email)

Add the current email to the component's email list.

Collecting emails during DFS builds the full set of emails belonging to one merged account.

for neighbor in graph[email]:

Iterate over all neighbors of the current email in the graph.

Exploring neighbors is essential to traverse the entire connected component of emails.

for email in graph:

Iterate over all emails in the graph to find unvisited starting points for DFS.

This loop ensures all connected components are found by starting DFS from each unvisited email.

for email in account[1:]:

Iterate over all emails in the current account starting from the first email.

This loop processes each email to build graph edges and map emails to names.

component_emails = []

Initialize a list to collect emails in the current connected component.

This list temporarily stores emails found by DFS before sorting and adding to results.

for account in accounts:

Iterate over each account in the input list.

Processing each account is necessary to build the graph and email-to-name mapping for all emails.

name = account[0]

Extract the account name from the first element of the account list.

The name is associated with all emails in the account and is needed for the email-to-name map.

res = []

Initialize a list to store the merged account results.

This list accumulates all merged accounts to be returned at the end.

return res

Return the list of merged accounts.

Returning the accumulated results completes the algorithm and provides the final answer.