What pattern does Minimize Malware Spread emphasize?

This problem focuses on array scanning plus hash lookup to track infection influence across nodes.

Why is DFS or BFS necessary in this problem?

DFS or BFS explores all nodes reachable from each initially infected node, helping calculate which nodes are uniquely infected.

How do I break ties if multiple nodes reduce the same malware count?

Return the node with the smallest index among candidates that achieve the maximum reduction.

Can this approach handle large graphs efficiently?

Yes, using O(N^2) time for adjacency matrix traversal and O(N) space for tracking unique influences works for graphs up to n=300.

What common mistakes should I avoid?

Avoid double-counting nodes infected by multiple sources, mishandling tie-breaking, and confusing total infections with unique influence counts.

#924

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

尽量减少恶意软件的传播

给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j 。一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个…

数组哈希表深度优先搜索广度优先搜索并查集

题目描述

给出了一个由 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 中所有整数均不重复

lightbulb

解题思路

方法一：并查集

根据题目描述，如果初始时有若干个节点属于同一个连通分量，那么一共可以分为三种情况：

这些节点中没有一个节点被感染
这些节点中只有一个节点被感染
这些节点中有多个节点被感染

我们要考虑的是，移除某个感染节点后，剩下的节点中被感染的节点数最少。

情况一没有被感染的节点，不需要考虑；情况二只有一个节点被感染，那么移除这个节点后，该连通分量中的其他节点都不会被感染；情况三有多个节点被感染，那么移除任意一个感染节点后，该连通分量中的其他节点还是会被感染，所以我们只需要考虑情况二。

我们利用并查集 $uf$ 维护节点的连通关系，用一个变量 $ans$ 记录答案，用一个变量 $mx$ 记录当前能减少感染的最大节点数，初始时 $ans = n$ , $mx = 0$ 。

然后遍历数组 $initial$ ，用一个哈希表或者一个长度为 $n$ 的数组 $cnt$ 统计每个连通分量中被感染节点的个数。

接下来，我们再遍历数组 $initial$ ，对于每个节点 $x$ ，我们找到其所在的连通分量的根节点 $root$ ，如果该连通分量中只有一个被感染节点，即 $cnt[root] = 1$ ，我们就更新答案，更新的条件是该连通分量中的节点数 $sz$ 大于 $mx$ 或者 $sz$ 等于 $mx$ 且 $x$ 的值小于 $ans$ 。

最后，如果 $ans$ 没有被更新，说明所有的连通分量中都有多个被感染节点，那么我们返回 $initial$ 中的最小值，否则返回 $ans$ 。

时间复杂度 $O(n^2 \times \alpha(n))$ ，空间复杂度 $O(n)$ 。其中 $n$ 是节点的个数，而 $\alpha(n)$ 是 Ackermann 函数的反函数。

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

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

class UnionFind:
    __slots__ = "p", "size"

    def __init__(self, n: int):
        self.p = list(range(n))
        self.size = [1] * n

    def find(self, x: int) -> int:
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a: int, b: int) -> bool:
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        return True

    def get_size(self, root: int) -> int:
        return self.size[root]


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        uf = UnionFind(n)
        for i in range(n):
            for j in range(i + 1, n):
                graph[i][j] and uf.union(i, j)
        cnt = Counter(uf.find(x) for x in initial)
        ans, mx = n, 0
        for x in initial:
            root = uf.find(x)
            if cnt[root] > 1:
                continue
            sz = uf.get_size(root)
            if sz > mx or (sz == mx and x < ans):
                ans = x
                mx = sz
        return min(initial) if ans == n else ans

speed

复杂度分析

指标	值
时间	complexity is O(N^2) because each node may require scanning all other nodes during DFS/BFS. Space complexity is O(N) to store infection counts and hash mappings for each node.
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Check if you track nodes influenced by multiple infections correctly.
question_mark
Verify that tie-breaking by node index is implemented consistently.
question_mark
Confirm that DFS/BFS does not revisit already processed nodes to avoid overcounting.

warning

常见陷阱

外企场景

error
Confusing total infections with uniquely influenced nodes leads to wrong removal choice.
error
Failing to handle tie-breaking properly can cause incorrect output.
error
Overcounting nodes visited by multiple DFS/BFS traversals inflates spread estimates.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider a variant where multiple nodes can be removed to minimize spread, introducing combinatorial evaluation.
arrow_right_alt
Change adjacency matrix to weighted connections, requiring adjusted spread influence calculation.
arrow_right_alt
Input as adjacency list instead of matrix, which may impact DFS/BFS implementation and performance.

help

常见问题

外企场景

继续练习

#928 尽量减少恶意软件的传播 II #959 由斜杠划分区域 #839 相似字符串组