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

难度: Hard

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

Submission

运行时间: 47 ms

内存: 20.3 MB

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        initial_record = [0] * n  # 记录感染节点集合，便于O(1)查询
        for i in initial:
            initial_record[i] = 1

        def dfs(node):
            if initial_record[node] == 1:
                return 0
            infect_node_num = 1
            visited[node] = 1
            for i in range(n):
                if graph[node][i] and visited[i] == 0:
                    next_infect_node_num = dfs(i)
                    if next_infect_node_num:
                        infect_node_num += next_infect_node_num
                    else:
                        visited[node] = 0  # 子节点有感染节点，需要当做没访问过来回溯
                        initial_record[node] = 1
                        return 0
            return infect_node_num

        ans = 500
        max_reduce_num = 1
        for infect_node in initial:
            visited = [0] * n
            reduce_num = 0
            visited[infect_node] = 1
            for next_node in range(n):  # 初始节点不写进dfs里是便于dfs过程中遇到感染节点直接返回0
                if graph[infect_node][next_node] and visited[next_node] == 0:
                    reduce_num += dfs(next_node)
            if reduce_num > max_reduce_num:
                ans = infect_node
                max_reduce_num = reduce_num
            elif reduce_num == max_reduce_num and infect_node < ans:
                ans = infect_node
        ans = ans if ans <= 300 else min(initial)
        return ans

Explain

这个题解的思路是通过深度优先搜索（DFS）来探索每个初始感染节点的影响范围，以确定在移除某个初始感染节点后，能够最大程度减少网络中感染的节点数量。首先，使用一个数组 `initial_record` 来标记哪些节点是初始感染节点。对每个初始感染节点进行测试，即假设将其移除，然后使用DFS来计算如果移除该节点后，由该节点直接或间接连接的节点中，有多少节点会被感染。对于每个通过DFS访问的节点，如果它是一个初始感染节点，就立即停止进一步的搜索。这样可以模拟该节点被移除后的情况。最后，选择能够使最终感染节点数最小化的节点，如果有多个节点都能达到最小化效果，则返回索引最小的节点。

时间复杂度: O(k * (n + m))

空间复杂度: O(n)

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        initial_record = [0] * n  # 记录初始感染节点
        for i in initial:
            initial_record[i] = 1

        def dfs(node):
            if initial_record[node] == 1:
                return 0  # 遇到初始感染节点，停止搜索
            infect_node_num = 1
            visited[node] = 1
            for i in range(n):
                if graph[node][i] and visited[i] == 0:
                    next_infect_node_num = dfs(i)
                    if next_infect_node_num:
                        infect_node_num += next_infect_node_num
                    else:
                        visited[node] = 0  # 回溯: 标记当前节点为未访问
                        initial_record[node] = 1  # 标记当前节点为感染
                        return 0
            return infect_node_num

        ans = 500
        max_reduce_num = 1
        for infect_node in initial:
            visited = [0] * n
            reduce_num = 0
            visited[infect_node] = 1
            for next_node in range(n):
                if graph[infect_node][next_node] and visited[next_node] == 0:
                    reduce_num += dfs(next_node)
            if reduce_num > max_reduce_num:
                ans = infect_node
                max_reduce_num = reduce_num
            elif reduce_num == max_reduce_num and infect_node < ans:
                ans = infect_node
        ans = ans if ans <= 300 else min(initial)
        return ans

Explore

在题解中，DFS用于估算移除某个初始感染节点后，其他节点受影响的程度。遇到其他初始感染节点时立即停止搜索是因为，如果不停止，我们会错误地计算由其他初始感染节点导致的感染范围作为当前考察节点的影响，这将导致结果不准确。此处理方式确保了我们只计算非初始感染节点的传播影响，从而准确评估在移除特定初始感染节点后，网络中感染的节点数的减少。

题解中的回溯操作似乎存在逻辑不一致。正常的回溯操作应该是在DFS完成后，将节点标记为未访问，以供其他DFS路径再次访问。而在题解中，回溯同时标记节点为感染和未访问，这是矛盾的。标记为感染应该表示节点在场景中是不可避免地被感染的，而标记为未访问则意味着该节点在后续的搜索中可以被重新探索。这种处理可能会导致算法在后续的执行中出现错误，如重复计算或逻辑判断错误。

题解通过模拟移除每个初始感染节点并使用DFS计算其影响范围来实现'最终感染节点数最小化'的目标。具体逻辑是：首先记录每个初始感染节点，然后逐个假设移除这些节点。对于每个假设移除的节点，使用DFS计算其直接或间接连接的非初始感染节点的数量。通过比较移除不同节点后的感染节点数量，选择能够使感染节点数最小化的节点。如果多个节点都能达到最小化效果，则返回索引最小的节点。这种方法通过直接计算每个操作的影响，找到最优解。