万州电商网站建设,中国建筑工程信息资讯网,教育培训网站源码,博客平台 wordpressLeetCode-924. 尽量减少恶意软件的传播【深度优先搜索 广度优先搜索 并查集 图 哈希表】 题目描述#xff1a;解题思路一#xff1a;解题思路二#xff1a;0解题思路三#xff1a;0 题目描述#xff1a;
给出了一个由 n 个节点组成的网络#xff0c;用 n n 个邻接矩阵图… LeetCode-924. 尽量减少恶意软件的传播【深度优先搜索 广度优先搜索 并查集 图 哈希表】 题目描述解题思路一解题思路二0解题思路三0 题目描述
给出了一个由 n 个节点组成的网络用 n × n 个邻接矩阵图 graph 表示。在节点网络中当 graph[i][j] 1 时表示节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接且其中至少一个节点受到恶意软件的感染那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续直到没有更多的节点可以被这种方式感染。
假设 M(initial) 是在恶意软件停止传播之后整个网络中感染恶意软件的最终节点数。
如果从 initial 中移除某一节点能够最小化 M(initial) 返回该节点。如果有多个节点满足条件就返回索引最小的节点。
请注意如果某个节点已从受感染节点的列表 initial 中删除它以后仍有可能因恶意软件传播而受到感染。
示例 1
输入graph [[1,1,0],[1,1,0],[0,0,1]], initial [0,1] 输出0 示例 2
输入graph [[1,0,0],[0,1,0],[0,0,1]], initial [0,2] 输出0 示例 3
输入graph [[1,1,1],[1,1,1],[1,1,1]], initial [1,2] 输出1
提示
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 中所有整数均不重复
解题思路一
一个大小为 k 的连通块内如果只有一个节点 x 被感染x 在 initial中那么移除 x 后这个连通块不会被感染从而让 M(initial)减少 k。
而如果连通块内至少有两个节点被感染无论移除哪个节点仍然会导致连通块被感染M(initial) 不变。
所以我们要找的是只包含一个被感染节点的连通块并且这个连通块越大越好。
算法如下
遍历 initial 中的节点 x。如果 x 没有被访问过那么从 x 开始 DFS同时用一个 vis 数组标记访问过的节点。DFS 过程中统计连通块的大小 size。DFS 过程中记录访问到的在 initial 中的节点。DFS 结束后如果发现该连通块只有一个在 initial 中的节点并且该连通块的大小比最大的连通块更大那么更新最大连通块的大小以及答案节点 x。如果一样大就更新答案节点的最小值。最后如果没找到符合要求的节点返回 min(initial)否则返回答案节点。
如何表达出「连通块内有一个或多个被感染的节点」呢要记录被感染的节点列表吗
其实无需记录节点列表而是用如下状态机 初始状态为 −1。 如果状态是 −1在找到被感染的节点 x 后状态变为 x。 如果状态是非负数 x在找到另一个被感染的节点后状态变为 −2。如果状态已经是 −2则不变。 此外可以用一个哈希表或者布尔数组记录哪些点在 initial 中从而在 DFS 中快速判断当前节点是否在 initial 中。
class Solution:def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) - int:st set(initial)vis [False] * len(graph)def dfs(x: int) - None:vis[x] Truenonlocal node_id, sizesize 1# 按照状态机更新 node_idif node_id ! -2 and x in st:node_id x if node_id -1 else -2for y, conn in enumerate(graph[x]):if conn and not vis[y]:dfs(y)ans -1max_size 0for x in initial:if vis[x]:continuenode_id -1size 0dfs(x)# 只包含一个被感染节点的连通块, 且包含节点数最大if node_id 0 and (size max_size or size max_size and node_id ans):ans node_idmax_size sizereturn min(initial) if ans 0 else ans时间复杂度O(n2) 空间复杂度O(n)
解题思路二0 时间复杂度O(n) 空间复杂度O(n)
解题思路三0 时间复杂度O(n) 空间复杂度O(n)
