How do I minimize malware spread in a network of nodes?

To minimize malware spread, you must determine which infected node to remove. Use graph traversal techniques like DFS or BFS to simulate the spread and assess the impact of removing each infected node.

What graph traversal techniques can I use for this problem?

You can use DFS (Depth-First Search) or BFS (Breadth-First Search) to traverse the graph and simulate the spread of malware, ensuring that all connections are considered when assessing node removal.

What should I do if multiple nodes result in the same infection count?

If multiple nodes lead to the same reduction in infection count, return the node with the smallest index to ensure an optimal solution.

How does removing a node affect the malware spread?

Removing a node reduces the number of nodes it can spread malware to, potentially halting the infection from reaching connected nodes. The impact is evaluated by simulating the spread after node removal.

What is the time complexity of solving this problem?

The time complexity of this problem is O(n^2) due to the graph traversal for each infected node and the simulation of the infection spread. Space complexity is also O(n^2) for storing the graph and infection states.

#928

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

尽量减少恶意软件的传播 II

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

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

题目描述

给定一个由 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 中每个整数都不同

lightbulb

解题思路

方法一：并查集

我们可以使用并查集，将所有不在 $initial$ 中的节点，并且满足 $graph[i][j] = 1$ 的节点 $(i, j)$ 进行合并。

接下来，我们创建一个哈希表 $g$ ，其中 $g[i]$ 表示所有与节点 $i$ 相连的连通分量的根节点。我们还需要一个计数器 $cnt$ ，用来统计每个根节点被多少个初始节点感染。

对于每个初始时被感染的节点 $i$ ，我们遍历所有与节点 $i$ 相连的节点 $j$ ，如果节点 $j$ 不在 $initial$ 中，我们将节点 $j$ 的根节点加入到集合 $g[i]$ 中。同时，我们统计每个根节点被多少个初始节点感染，将结果保存到计数器 $cnt$ 中。

然后，我们用一个变量 $ans$ 记录答案，用 $mx$ 记录最多可以减少的被感染节点的数量。初始时 $ans = 0$ , $mx = -1$ 。

遍历所有初始时被感染的节点，对于每个节点 $i$ ，我们遍历 $g[i]$ 中的所有根节点，如果根节点只被一个初始节点感染，我们累加这个根节点所在的连通分量的大小到 $t$ 中。如果 $t > mx$ 或者 $t = mx$ 且 $i < ans$ ，我们更新 $ans = i$ , $mx = t$ 。

最后返回 $ans$ 即可。

时间复杂度 $O(n^2 \times \alpha(n))$ ，空间复杂度 $O(n^2)$ 。其中 $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

48

49

50

51

52

53

54

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)
        s = set(initial)
        uf = UnionFind(n)
        for i in range(n):
            if i not in s:
                for j in range(i + 1, n):
                    graph[i][j] and j not in s and uf.union(i, j)

        g = defaultdict(set)
        cnt = Counter()
        for i in initial:
            for j in range(n):
                if j not in s and graph[i][j]:
                    g[i].add(uf.find(j))
            for root in g[i]:
                cnt[root] += 1

        ans, mx = 0, -1
        for i in initial:
            t = sum(uf.get_size(root) for root in g[i] if cnt[root] == 1)
            if t > mx or (t == mx and i < ans):
                ans, mx = i, t
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates knowledge of graph traversal algorithms like DFS and BFS.
question_mark
The candidate can efficiently evaluate the impact of node removal in a graph with multiple infected nodes.
question_mark
The candidate correctly optimizes for the minimum number of infections after node removal.

warning

常见陷阱

外企场景

error
Failing to account for the spread of malware from all initially infected nodes and only considering the first infected node.
error
Overlooking edge cases where removing a node does not reduce the number of infections.
error
Not properly simulating the infection spread after node removal, leading to incorrect calculations of the final result.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider variations where the number of initially infected nodes can vary or where different network topologies are used.
arrow_right_alt
Extend the problem to handle multiple malware types or sources of infection.
arrow_right_alt
Alter the problem to allow multiple nodes to be removed and find the combination that minimizes malware spread.

help

常见问题

外企场景

继续练习

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