[leetcode/lintcode 题解] 尽量减少恶意软件的传播II 算法 刷题解法

DanielZhao 20天前 54


(这个问题与 尽量减少恶意软件的传播 是一样的,不同之处用粗体表示。)

在节点网络中,只有当graph[i][j] = 1 时,每个节点i能够直接连接到另一个节点j

一些节点initial最初被恶意软件感染。只要两个节点直接连接,且其中至少一个节点受到恶意软件的感染,那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续,直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后,整个网络中感染恶意软件的最终节点数。

我们可以从初始列表中删除一个节点,并完全移除该节点以及从该节点到任何其他节点的任何连接。如果移除这一节点将最小化 M(initial), 则返回该节点。如果有多个节点满足条件,就返回索引最小的节点。

  1. 1 < graph.length = graph[0].length <= 300
  2. 0 <= graph[i][j] == graph[j][i] <= 1
  3. graph[i][i] = 1
  4. 1 <= initial.length < graph.length
  5. 0 <= initial[i] < graph.length

在线评测地址: https://www.lintcode.com/problem/minimize-malware-spread-ii/?utm_source=sc-xytsq-zq

样例 1:

样例 2:

考点:

  • 图论
  • 搜索

题解:要想把一个点从本来要被感染的状态变成不被感染,那么需要把能把它感染的结点全部删除!!!

如果一个结点能够被两个或更多感染结点从不同的路径感染,那么这个结点是不可能安全的。如下图所示,其中黄色结点是初始被感染结点:

对于1结点来说,0,4能从不同的路径将其感染,即使删除一个,另一个也会将其感染。

对于6节点来说,虽然0,4也能将其感染,但是是从相同路径(要经过4),也就是如果我们删除4,即可避免6被感染!

所以我们要找的就是那些只会被一个结点感染的点(如图中的6),然后存储那个唯一可以感染他的结点,我们采用bfs来完成。如果在bfs过程中遍历到其他被感染结点则不再遍历下去。

最后我们统计存储的结点中哪个结点出现得最多即可,如果都是0则输出index最小的结点。

更多语言代码参见:https://www.jiuzhang.com/solution/minimize-malware-spread-ii/?utm_source=sc-xytsq-zq

最新回复 (0)
返回