Leetcode 928 Minimize Malware Spread II

发表于 |

(这个问题与 尽量减少恶意软件的传播 是一样的，不同之处用粗体表示。)
在节点网络中，只有当 graph[i][j] = 1 时，每个节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
我们可以从初始列表中删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。如果移除这一节点将最小化 M(initial)， 则返回该节点。如果有多个节点满足条件，就返回索引最小的节点。

示例 1：
输出：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输入：0

示例 2：
输入：graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
输出：1

示例 3：
输入：graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
输出：1

提示：

  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://buptwc.github.io/2018/10/15/Leetcode-924-Minimize-Malware-Spread/

这道题关键点在于想到，要想把一个点从本来要被感染的状态变成不被感染，那么需要把能把它感染的结点全部删除！！！

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

对于1结点来说，0,4能从不同的路径将其感染，即使删除一个，另一个也会将其感染。
对于6节点来说，虽然0,4也能将其感染，但是是从相同路径（要经过4），也就是如果我们删除4,即可避免6被感染！

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 492ms
import collections
class Solution(object):
    def minMalwareSpread(self, graph, initial):
        n = len(graph)
        d = collections.defaultdict(list)
        # 对每个初始感染节点依次bfs，因为节点总数不超过300，所以不会超时
        for init in initial:
            vis = set(initial)
            Q = collections.deque([init])
            while Q:
                infect = Q.popleft()
                for node in range(len(graph[infect])):
                    if graph[infect][node] == 0: continue
                    if node in vis: continue
                    vis.add(node)
                    d[node].append(init)
                    Q.append(node)
        # 统计出现最多次的感染节点
        res = [0] * n
        for key in d:
            if len(d[key]) == 1:
                res[d[key][0]] += 1
        if max(res) == 0: return min(initial)
        return res.index(max(res))