**Accounts Merge** https://leetcode.com/problems/accounts-merge/description/

**Finding Components Using DFS**

- Build a undirectional graph by iterating all the accounts. The index of the sublist within the accounts array can be used as account id. If an email was found in accounts 1, 2 and is found again in account 3, then 3 is a nbr of 1, 2 and 1,2 are nbr of 3.
- Once we built the graph, simply run dfs on it and get all the components.
- Once we have the components, identify all the unique emails and format the result. Notice the use of itertools in formatting.

```
from collections import defaultdict
from itertools import chain
class Solution(object):
def dfs(self, root, graph, visited, component):
visited.add(root)
component.append(root)
for nbr in graph[root]:
if nbr not in visited:
self.dfs(nbr, graph, visited, component)
return
def build_graph(self, accounts):
graph, dedupe = {}, defaultdict(list)
for idx, account in enumerate(accounts):
graph[idx] = set([])
for email in account[1:]:
if email in dedupe:
for nbr in dedupe[email]:
graph[idx].add(nbr)
graph[nbr].add(idx)
dedupe[email].append(idx)
return graph
def identify_components(self, graph):
visited = set([])
components = []
for root in graph.keys():
if root not in visited:
component = []
self.dfs(root, graph, visited, component)
components.append(component)
return components
def format_result(self, components, accounts):
result = []
for component in components:
emails = sorted(list(set(chain(*(accounts[i][1:] for i in component)))))
result.append([accounts[component[0]][0]] + emails)
return result
def accountsMerge(self, accounts):
"""
:type accounts: List[List[str]]
:rtype: List[List[str]]
"""
graph = self.build_graph(accounts)
components = self.identify_components(graph)
result = self.format_result(components, accounts)
return result
```