-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
928.py
87 lines (73 loc) · 2.6 KB
/
928.py
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
__________________________________________________________________________________________________
sample 1124 ms submission
from collections import defaultdict
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
g = [set() for _ in range(len(graph))]
#initial = set(initial)
for i, connections in enumerate(graph):
g[i] = {k for k, conn in enumerate(connections) if conn == 1 and k != i}
def bfs(k):
queue = initial[::]
res = 0
used = set(queue)
for i in queue:
if i == k:
continue
res += 1
for j in g[i]:
if j not in used:
queue.append(j)
used.add(j)
return res
#print(g)
res, cnt = -1, float('inf')
for i in sorted(initial):
cand = bfs(i)
#print(i, cand)
if cand < cnt:
res, cnt = i, cand
return res
__________________________________________________________________________________________________
sample 15000 kb submission
class Solution:
def minMalwareSpread(self, graph, initial):
source = collections.defaultdict(list)
initial.sort()
#print(initial)
for i_node in initial:
q = collections.deque()
q.append(i_node)
visited = set(initial)
while len(q):
node = q.popleft()
for other_node, conn in enumerate(graph[node]):
#print(other_node, conn, node)
if not conn:
continue
if other_node in visited:
continue
visited.add(other_node)
source[other_node].append(i_node)
q.append(other_node)
#print(source)
d = collections.defaultdict(int)
for node, nodes_list in source.items():
#print("nl", nodes_list)
if len(nodes_list) == 1:
d[nodes_list[0]] += 1
#print("d", d)
mmax = 0
res = -1
for node in d:
if d[node] > mmax:
res = node
mmax = d[node]
elif d[node] == mmax:
res = min(res, node)
#print("res", res, mmax)
#print("", res)
if res == -1:
return initial[0]
return res
__________________________________________________________________________________________________