题目:
给出了一个由 n
个节点组成的网络,用 n × n
个邻接矩阵图 graph
表示。在节点网络中,当 graph[i][j] = 1
时,表示节点 i
能够直接连接到另一个节点 j
。
一些节点 initial
最初被恶意软件感染。只要两个节点直接连接,且其中至少一个节点受到恶意软件的感染,那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续,直到没有更多的节点可以被这种方式感染。
假设 M(initial)
是在恶意软件停止传播之后,整个网络中感染恶意软件的最终节点数。
如果从 initial
中移除某一节点能够最小化 M(initial)
, 返回该节点。如果有多个节点满足条件,就返回索引最小的节点。
请注意,如果某个节点已从受感染节点的列表 initial
中删除,它以后仍有可能因恶意软件传播而受到感染。
提示:
n == graph.length
n == graph[i].length
2 <= n <= 300
graph[i][j] == 0
或1
.graph[i][j] == graph[j][i]
graph[i][i] == 1
1 <= initial.length <= n
0 <= initial[i] <= n - 1
initial
中所有整数均不重复
思考:
由题意“只要两个节点直接连接,且其中至少一个节点受到恶意软件的感染,那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续,直到没有更多的节点可以被这种方式感染”可知,将图中所有彼此有路径到达的节点们看成一组,如果一组中有至少一个节点初始时被感染,那么这一组所有节点最后都会被感染。
我们要使得最后被感染的总节点数最少,就要找到这样一个组:
- 组内只有一个节点最初被感染
- 组内节点数尽可能多
如果这样的组只有一个,直接返回其最初感染的节点索引;如果这样的组有多个(节点数同样最多),在他们各自的最初感染的节点中选择索引最小的那个返回;如果不存在这样的组,则返回initial中索引最小的点。(*)
那么我们的算法步骤如下:
1. 遍历initial中的每个节点node。
2. 对每个node,计算它所在的组包含的节点数量,步骤见下文。如果node所在的组之前已经计算过,则不需要重复计算。用字典记录组:键——node;值——[组的节点数量,组内属于initial的节点数量]。用数组visited记录每个节点是否被访问过。
3. 在这些组中依据上文中(*)段的内容返回相应的值。
第2步中具体的计算步骤如下:
1. 用队列queue记录待判断的节点,初始为{node},组内节点数nodes_count初始为1,组内属于initial的节点数nodes_initial初始为1。
2. 每次从队列queue中弹出一个节点x,将x的visited置为已访问。遍历其余所有节点k:如果节点k还未访问过,且与节点x相邻,则将节点k加入队列queue,组内节点数nodes_count加一,如果节点k属于initial,则nodes_initial加一。
3. 直到queue为空为止,返回node所在组的组内节点数nodes_count,组内属于initial的节点数nodes_initial。
代码如下:
from collections import deque
class Solution(object):
def minMalwareSpread(self, graph, initial):
"""
:type graph: List[List[int]]
:type initial: List[int]
:rtype: int
"""
# 将互相能到达的节点们视为一个组,(如果initial中有属于这一组的节点)每组的节点数量即为这一个小网络的感染恶意软件的最终节点数
n = len(graph)
sum_dict = {} # 字典sum_dict记录每组的索引最小的节点(键),节点数量(值1)和属于initial的节点数量(值2)
visited = [-1] * n # 数组visited记录节点是否访问过(已计算出相连节点数)
def connectedNodes(graph, initial, node): # 函数统计组内节点数
queue = deque() # 队列储存待判断相邻节点的节点
queue.append(node)
nodes_count = 1
nodes_initial = 1
while queue:
x = queue.popleft()
visited[x] = 1
for k in range(n):
if k == x: # 跳过当前节点本身
continue
if visited[k] != 1 and graph[x][k] == 1 and k not in queue:
# 将当前节点的相邻且未访问过的节点加入队列,组内节点数加一
nodes_count += 1
queue.append(k)
if k in initial:
nodes_initial += 1
return nodes_count, nodes_initial
for i in initial:
if visited[i] == -1:
nodes_count, nodes_initial = connectedNodes(graph, initial, i)
sum_dict[i] = [nodes_count, nodes_initial]
count = 0
res = min(initial)
for node, value in sum_dict.items():
# 在字典中找到某一组满足条件:属于initial的节点只有一个(值2)且节点数(值1)最多
# 如果存在这样的组,返回这一字典项的键;如果不存在这样的组,则返回0
if value[1] == 1:
if count < value[0]:
res = node
count = value[0]
return res
提交通过,自己做出来困难题真开心嘿嘿: