怎么找合适的网站开发,微信小程序组件库,中国外贸人才网,企业机房建设公司题目#xff1a;
给出了一个由 n 个节点组成的网络#xff0c;用 n n 个邻接矩阵图 graph 表示。在节点网络中#xff0c;当 graph[i][j] 1 时#xff0c;表示节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接#x…题目
给出了一个由 n 个节点组成的网络用 n × n 个邻接矩阵图 graph 表示。在节点网络中当 graph[i][j] 1 时表示节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接且其中至少一个节点受到恶意软件的感染那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续直到没有更多的节点可以被这种方式感染。
假设 M(initial) 是在恶意软件停止传播之后整个网络中感染恶意软件的最终节点数。
如果从 initial 中移除某一节点能够最小化 M(initial) 返回该节点。如果有多个节点满足条件就返回索引最小的节点。
请注意如果某个节点已从受感染节点的列表 initial 中删除它以后仍有可能因恶意软件传播而受到感染。
提示
n graph.lengthn graph[i].length2 n 300graph[i][j] 0 或 1.graph[i][j] graph[j][i]graph[i][i] 11 initial.length n0 initial[i] n - 1initial 中所有整数均不重复 思考
由题意“只要两个节点直接连接且其中至少一个节点受到恶意软件的感染那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续直到没有更多的节点可以被这种方式感染”可知将图中所有彼此有路径到达的节点们看成一组如果一组中有至少一个节点初始时被感染那么这一组所有节点最后都会被感染。
我们要使得最后被感染的总节点数最少就要找到这样一个组
组内只有一个节点最初被感染 组内节点数尽可能多
如果这样的组只有一个直接返回其最初感染的节点索引如果这样的组有多个节点数同样最多在他们各自的最初感染的节点中选择索引最小的那个返回如果不存在这样的组则返回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 dequeclass 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的节点数量值2visited [-1] * n # 数组visited记录节点是否访问过已计算出相连节点数def connectedNodes(graph, initial, node): # 函数统计组内节点数queue deque() # 队列储存待判断相邻节点的节点queue.append(node)nodes_count 1nodes_initial 1while queue:x queue.popleft()visited[x] 1for k in range(n):if k x: # 跳过当前节点本身continueif visited[k] ! 1 and graph[x][k] 1 and k not in queue:# 将当前节点的相邻且未访问过的节点加入队列组内节点数加一nodes_count 1queue.append(k)if k in initial:nodes_initial 1return nodes_count, nodes_initialfor i in initial:if visited[i] -1:nodes_count, nodes_initial connectedNodes(graph, initial, i)sum_dict[i] [nodes_count, nodes_initial]count 0res min(initial)for node, value in sum_dict.items():# 在字典中找到某一组满足条件属于initial的节点只有一个(值2)且节点数(值1)最多# 如果存在这样的组返回这一字典项的键如果不存在这样的组则返回0if value[1] 1:if count value[0]:res nodecount value[0]return res
提交通过自己做出来困难题真开心嘿嘿
