forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathaccounts-merge.py
More file actions
executable file
·134 lines (108 loc) · 3.91 KB
/
accounts-merge.py
File metadata and controls
executable file
·134 lines (108 loc) · 3.91 KB
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
"""
Treat each email as a node.
Build an adjacency graph. [0]
For every account's data
First, lets check if the first email is already merged. [1]
If the first email is already merged to other groups, then other emails will be in another group as well.
So don't need to check.
Second, do a DFS starting from the first email. Put all the connected nodes into visited. [2]
And append the sorted(visited) to the ans with name. [3]
Let N be the total number of emails. M be the total number of final groups.
Build the graph takes O(N).
For each final groups, we make a DFS to all nodes, taking O(MN).
Sort the group takes O((N/M)*Log(N/M)) -> O((N/M)*(logN-LogM))
Time: O(MN)
Space: O(N)
"""
from collections import defaultdict
class Solution(object):
def accountsMerge(self, accounts):
graph = defaultdict(list)
merged = set()
ans = []
#[0]
for data in accounts:
emails = data[1:]
for i, email in enumerate(emails):
graph[email].extend(emails[:i])
graph[email].extend(emails[i+1:])
for data in accounts:
name = data[0]
visited = set()
stack = [data[1]] #[2]
if data[1] in merged: continue #[1]
while stack:
e = stack.pop()
if e in visited: continue
visited.add(e)
stack.extend(graph[e])
merged.update(visited)
ans.append([name]+sorted(list(visited))) #[3]
return ans
#Union Find
class Solution(object):
def accountsMerge(self, accounts):
def find(x):
p = parents[x]
while p!=parents[p]:
p = find(p)
parents[x] = p
return p
def union(x, y):
p1, p2 = find(x), find(y)
if p1==p2: return
parents[p2] = p1
parents = {}
mailToName = {}
for account in accounts:
name = account[0]
root = account[1]
if root not in parents: parents[root] = root
root = find(root)
mailToName[root] = name
for i in xrange(2, len(account)):
email = account[i]
if email in parents:
union(parents[email], root)
root = find(root)
parents[email] = root
rootToMails = collections.defaultdict(list)
for email in parents:
rootToMails[find(email)].append(email)
ans = []
for root in rootToMails:
name = mailToName[root]
mails = rootToMails[root]
ans.append([name]+sorted(mails))
return ans
#DFS
class Solution(object):
def accountsMerge(self, accounts):
#build adjacency list
adj = collections.defaultdict(list)
for account in accounts:
name = account[0]
email0 = account[1]
for i in xrange(2, len(account)):
email = account[i]
adj[email0].append(email)
adj[email].append(email0)
#iterate accounts and dfs each email group
ans = []
visited = set() #store all the visited email
for account in accounts:
name = account[0]
email0 = account[1]
if email0 in visited: continue
#dfs
group = set() #store the email group related to email0
stack = [email0]
while stack:
email = stack.pop()
if email in group or email in visited: continue
group.add(email)
visited.add(email)
for nei in adj[email]:
stack.append(nei)
ans.append([name]+sorted(list(group)))
return ans