难度: Hard
原题连接
内容描述
(This problem is the same as Minimize Malware Spread, with the differences bolded.)
In a network of nodes, each node i is directly connected to another node j if and only if graph[i][j] = 1.
Some nodes initial are initially infected by malware. Whenever two nodes are directly connected and at least one of those two nodes is infected by malware, both nodes will be infected by malware. This spread of malware will continue until no more nodes can be infected in this manner.
Suppose M(initial) is the final number of nodes infected with malware in the entire network, after the spread of malware stops.
We will remove one node from the initial list, completely removing it and any connections from this node to any other node. Return the node that if removed, would minimize M(initial). If multiple nodes could be removed to minimize M(initial), return such a node with the smallest index.
Example 1:
Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0
Example 2:
Input: graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
Output: 1
Example 3:
Input: graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
Output: 1
Note:
1 < graph.length = graph[0].length <= 300
0 <= graph[i][j] == graph[j][i] <= 1
graph[i][i] = 1
1 <= initial.length < graph.length
0 <= initial[i] < graph.length
思路 1 - 时间复杂度: O(len(graph)^2 * len(initial))- 空间复杂度: O(len(graph))******
这道题跟第924题的区别在于924题目中的这句话：
Note that if a node was removed from the initial list of infected nodes,
it may still be infected later as a result of the malware spread.
以及928题目里面的这句话：
We will remove one node from the initial list, completely removing it and any connections from this node to any other node.
因此如果928里面一个initial的node被删除掉之后，那么通过这个node去感染别的node也不可以了，相当于直接隔离了这个点。
因此我们就模拟这个过程，对initial做一个遍历，每次隔离掉一个点，然后看隔离掉哪个点所导致最终的infects最少，就返回哪个点
class Solution(object):
def minMalwareSpread(self, graph, initial):
"""
:type graph: List[List[int]]
:type initial: List[int]
:rtype: int
"""
def find(x):
while x != uf[x]:
uf[x] = uf[uf[x]]
x = uf[x]
return uf[x]
def union(x, y):
x_root = find(x)
y_root = find(y)
uf[x_root] = y_root
size[y_root] += size[x_root]
def connected(x, y):
return find(x) == find(y)
def helper(graph, initial, node):
for i in range(len(graph)):
for j in range(i+1, len(graph)):
if graph[i][j] and i != node and j != node:
if not connected(i, j): # 没联通才联通，避免重复更新size列表
union(i, j)
seen = [False] * len(graph)
infects = 0
for ini in initial:
if ini == -1: # 代表这个点被隔离了
continue
root = find(ini)
if seen[root]: # 避免重复计算感染数量
continue
seen[root] = True
infects += size[root] # 只要有initial里面元素在该联通分量里面，这整个联通分量都会被感染
return infects
initial.sort() # 这样最后会返回最小的index
res, min_ = initial[0], sys.maxsize
uf = [i for i in range(len(graph))] # 定义我们的uf与size列表
size = [1] * len(graph)
for idx, node in enumerate(initial):
initial[idx] = -1 # 隔离这个点
infects = helper(graph, initial, node)
uf = [i for i in range(len(graph))] # 需要reset我们的uf与size列表
size = [1] * len(graph)
if infects < min_:
min_ = infects
res = node
initial[idx] = node # 恢复这个点
return res