1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
# 721. Accounts Merge
from collections import defaultdict
"""
given a list of 'accounts' where 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. now we would like
to merge these accounts. two accounts definitely bbelong to the same person
if there is some common email to bboth accounts. note that even if two
accounts have the same name, they may belong to different people as people
could have the same name. a person can have any numbber of accounts initially
but all of their accounts definitely have the same name. after merging the
accounts, return the accounts in the following format: the first element of
each accout is the name, and the rest of the elements are emails in sorted
order. the accounts themselves can e returned in any order.
"""
class union_find:
def __init__(self, n):
self.parents = list(range(n))
def union(self, child, parent):
self.parents[self.find(child)] = self.find(parent)
def find(self, x):
if x != self.parents[x]:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
class Solution(object):
def accountsMerge(self, accounts):
"""
:type accounts: List[List[str]]
:rtype: List[List[str]]
"""
uf = union_find(len(accounts))
ownership = {}
for i, (_, *emails) in enumerate(accounts):
for email in emails:
if email in ownership:
uf.union(i, ownership[email])
ownership[email] = i
ans = defaultdict(list)
for email, owner in ownership.items():
ans[uf.find(owner)].append(email)
return [[accounts[i][0]] + sorted(emails) for i, emails in ans.items()]
if __name__ == "__main__":
obj = Solution()
print(
obj.accountsMerge(
accounts=[
["John", "[email protected]", "[email protected]"],
["John", "[email protected]", "[email protected]"],
["Mary", "[email protected]"],
["John", "[email protected]"],
]
)
)
print(
obj.accountsMerge(
accounts=[
["Gabe", "[email protected]", "[email protected]", "[email protected]"],
["Kevin", "[email protected]", "[email protected]", "[email protected]"],
["Ethan", "[email protected]", "[email protected]", "[email protected]"],
["Hanzo", "[email protected]", "[email protected]", "[email protected]"],
["Fern", "[email protected]", "[email protected]", "[email protected]"],
]
)
)
|