forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 1
/
minimize-malware-spread-ii.py
62 lines (53 loc) · 1.94 KB
/
minimize-malware-spread-ii.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
# Time: O(n^2)
# Space: O(n)
import collections
class UnionFind(object):
def __init__(self, n):
self.set = range(n)
def find_set(self, x):
if self.set[x] != x:
self.set[x] = self.find_set(self.set[x]) # path compression.
return self.set[x]
def union_set(self, x, y):
x_root, y_root = map(self.find_set, (x, y))
if x_root == y_root:
return False
self.set[min(x_root, y_root)] = max(x_root, y_root)
return True
class Solution(object):
def minMalwareSpread(self, graph, initial):
"""
:type graph: List[List[int]]
:type initial: List[int]
:rtype: int
"""
initial_set = set(initial)
clean = [i for i in xrange(len(graph)) if i not in initial_set]
union_find = UnionFind(len(graph))
for i in xrange(len(clean)):
for j in xrange(i+1, len(clean)):
if graph[clean[i]][clean[j]] == 1:
union_find.union_set(clean[i], clean[j])
union_size = collections.Counter(union_find.find_set(i) for i in xrange(len(graph)))
shared_union = collections.defaultdict(set)
for i in initial:
for j in clean:
if graph[i][j] == 1:
x = union_find.find_set(j)
shared_union[x].add(i)
result, total = float("inf"), float("-inf")
for i in initial:
lookup = set()
curr = 0
for j in clean:
if graph[i][j] == 1:
x = union_find.find_set(j)
if len(shared_union[x]) == 1 and \
x not in lookup:
curr += union_size[x]
lookup.add(x)
if curr > total or \
(curr == total and i < result):
total = curr
result = i
return result