accounts merge

Go Back home
 1 import collections
 2 
 3 def accountsMerge( accounts):
 4     em_to_name = {}
 5     graph = collections.defaultdict(set)
 6     for acc in accounts:
 7         em_to_name[acc[1]] = acc[0]
 8         for email in acc[1:]:
 9             graph[acc[1]].add(email)
10             graph[email].add(acc[1])
11 
12     def visit(email):
13         seen.add(email)
14         for next_node in graph[email]:
15             if next_node not in seen:
16                 visit(next_node)
17 
18     seen, done, ans = set(), set(), []
19     for email in em_to_name:
20         if email not in done:
21             visit(email)
22             ans.append([em_to_name[email]] + [*sorted([*seen])])
23             done.update(seen)
24             seen.clear()
25     return ans
26 
27 r = accountsMerge([
28                 ["David", "d0", "d1", "d3"],
29                 ["David", "d1", "d2"],
30                 ["Mary", "m1", "m2"],
31                 ["Mary", "m2"]])
32 print(r)

1 r = accountsMerge([
2                 ["David", "d0", "d1", "d3"],
3                 ["David", "d1", "d2"],
4                 ["David", "d4", "d2"],
5                 ["David", "d5", "d2"],
6                 ["David", "d0", "d2"],
7                 ["David", "d0", "d2", "d7"],
8                 ["Mary", "m1", "m2"],
9                 ["Mary", "m2"]])
graph TD d0 --> d1 d7 --> d0 d0 --> d2 d0 --> d0 d5 --> d2 d2 --> d4 d1 --> d0 d4 --> d4 d2 --> d1 d0 --> d7 d2 --> d5 d0 --> d3 d1 --> d1 d2 --> d0 d3 --> d0 d1 --> d2 d4 --> d2 d5 --> d5
graph TD m2 --> m1 m1 --> m1 m2 --> m2 m1 --> m2

See also:

alien dictionary