题目描述
给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示。在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
我们可以从 initial 中删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。
请返回移除后能够使 M(initial) 最小化的节点。如果有多个节点满足条件，返回索引 最小的节点 。
思路
和上一道题 924. 尽量减少恶意软件的传播不同的是，这一道题可以“从 initial 中删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。”，其实我在做上一道题的时候错误地理解成这一道题了。
我们用 DFS 完成了 924，在 DFS 中记录了当前 initial[i] 值的状态。对于这道题，朴素的想法是每次移除一个 initial 节点后 DFS，那么这样我们需要做 len(initial) 次 DFS，时间复杂度可能会比较高，有没有可能一次 DFS 就可以完成呢？
感觉是可以的。如果我们移除了所有 initial 中的节点（做标记），然后对剩下的节点进行 DFS，在 DFS 中，记录本次 DFS 能访问到的节点数量和能访问的 initial 中的节点数量：
- 如果访问不到
initial节点，非常好； - 如果访问 1 个
initial节点，考虑将它移除； - 如果访问 1 个以上
initial节点，没得救，随便移除哪个都行。
那么整体逻辑和之前似乎大差不差，先实现 DFS：
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
l = len(graph)
visited = [False] * l
st = set(initial)
def dfs(node):
visited[node] = True
for idx, conn in enumerate(graph[node]):
if conn == 0:
continue
if idx in st:
continue
if not visited[idx]:
dfs(idx)
for node in range(l):
if visited[node] or node in st:
continue
dfs(node)因为我们假装把 initial 中的值都移除了，因此这里 dfs 的时候要跳过。
接下来往上加东西。和 924 差不多，我们要添加一次 DFS 能够访问的节点数量和一次 DFS 能遇到的 initial 节点数量：
Warning
这里我忘了一点，DFS 的时候有可能会多次访问同一个 initial 节点
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
l = len(graph)
visited = [False] * l
st = set(initial)
def dfs(node):
visited[node] = True
nonlocal size, status
size += 1
for idx, conn in enumerate(graph[node]):
if conn == 0:
continue
if idx in st:
if status != -2 and status != idx:
if status == -1:
status = idx
else:
status = -2
continue
if not visited[idx]:
dfs(idx)
for node in range(l):
size = 0
status = -1
if visited[node] or node in st:
continue
dfs(node)最后是 DFS 后处理。在只会访问到一个 initial 节点的情况下能被访问到的节点数量越多越好。但是可能多次 DFS 都会访问到某一个 initial 节点，因此我们需要一个计数器保存能被访问到的 initial 节点数量，在最后取最大值。
最终代码：
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
l = len(graph)
visited = [False] * l
st = set(initial)
def dfs(node):
visited[node] = True
nonlocal size, status
size += 1
for idx, conn in enumerate(graph[node]):
if conn == 0:
continue
if idx in st:
if status != -2 and status != idx:
if status == -1:
status = idx
else:
status = -2
elif not visited[idx]:
dfs(idx)
cnt = Counter()
for node in range(l):
size = 0
status = -1
if visited[node] or node in st:
continue
dfs(node)
if status >= 0:
cnt[status] += size
if not cnt:
return min(initial)
return min([(-size, node) for node, size in cnt.items()])[1]最后一段参考 https://leetcode.cn/problems/minimize-malware-spread-ii/solutions/2743395/ni-xiang-si-wei-pythonjavaccgojsrust-by-jinc3。我们希望返回 cnt 中值最大的，如果值相同时返回最小的，那么就可以将 size 取负数，将问题转换成 (-size, node) 中最小的，然后返回第二个元素也就是节点位置。这个很 tricky，如果我们不这样写的话要写很多行代码，但如果这样写的话需要花一些时间理解，只能说有利有弊吧。