0928：尽量减少恶意软件的传播 II（1985 分）

力扣第 107 场周赛第 4 题

题目

给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示。在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。

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

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

我们可以从 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

提示：

• 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 中每个整数都不同

分析

• 与 0924 的区别在于删除恶意节点是完全删除
• 因此先考虑去掉所有恶意节点时的连通状态
• 然后考虑某一恶意节点 i，设其和某个连通块 a 相连
  • 假如 a 和不止一个恶意节点相连，删除 i 无意义
  • 假如 a 只和 i 一个恶意节点相连，删除 i 则 a 的节点都不会被感染
  • 遍历和 i 相连的所有连通块，即得到删除 i 后 M 的减少量
• 遍历恶意节点并比较即可

解答

 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

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        def find(x):
            if f[x] != x:
                f[x] = find(f[x])
            return f[x]
        
        def union(x,y):
            f[find(x)] = find(y)
        
        n = len(graph)
        f, vis = list(range(n)), set(initial)
        for i,j in product(range(n),range(n)):
            if graph[i][j] and i not in vis and j not in vis:
                union(i,j)
        sz,g = [0]*n,[set() for _ in range(n)]
        for i in range(n):
            if i not in vis:
                sz[find(i)] += 1
                g[find(i)] |= {j for j in vis if graph[i][j]}
        d = [0]*n
        for i in range(n):
            if len(g[i])==1:
                d[g[i].pop()] += sz[i]
        return max(sorted(initial),key=lambda i:d[i])

39 ms