题目描述
给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。
请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。
思路
题目的要求是如果移除某个节点能够使网络中感染恶意软件的最终节点数最少，就返回这个节点。
如果在最开始有若干节点属于同一个连通分量，那么考虑一下几种情况：
- 如果网络中没有被感染的节点，那么不需要考虑；
- 如果网络中有一个被感染的节点，只需要移除这一个节点；
- 如果网络中有多个节点被感染，移除一个后其他的还是会被感染；
因此我们只需要考虑情况 2。
疑惑
对下图的情况，该怎么考虑呢？
如果 C 和 D 是被感染的节点，此时图中有多个节点被感染，属于上述的第 3 种情况。如果我们移除 C，那么图会被分为两个分量，左边的分量不会被感染，右边的分量会被感染，这种情况怎么做呢？
回答
原来是我理解的有问题，移除指的是从
initial数组中移除，意思就是说相当于没有病毒，但是节点还在图中。因此对于上面的图，无论移除哪一个点（只消灭了一个节点的病毒）都无法避免之后被感染的可能，因此对于上面的例子，按照题目要求应该移除最小的带病毒的点。
那这样的话我们其实可以对 initial 数组中的元素进行 DFS，去判断 initial 对应的连通分量是否有多于一个被感染的节点：
- 如果对每个
initial中的元素都有且仅有一个的话，选择连通分量最大的节点； - 否则优先选择只有一个被感染元素的节点；
- 要是都多于一个就随便选了。
那么重点在于怎么构建并保存这些中间变量了。考虑一下我们都需要哪些信息：
- DFS 时记录当前连通分量的节点数量；
- DFS 时记录有多少个节点在
initial中；
不如先实现一个简单的 DFS 吧，访问 initial 中的所有节点：
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
n = len(graph)
visited = [False] * n
def dfs(node):
visited[node] = True
for idx, conn in enumerate(graph[node]):
if conn and not visited[idx]:
dfs(idx)
for node in initial:
if visited[node]:
continue
dfs(node)为了记录当前 DFS 过的块数，我们需要通过一个 size 记录：
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
n = len(graph)
visited = [False] * n
def dfs(node):
visited[node] = True
nonlocal size
size += 1
for idx, conn in enumerate(graph[node]):
if conn and not visited[idx]:
dfs(idx)
for node in initial:
if visited[node]:
continue
size = 0
dfs(node)
为了判断是否有被感染的节点，我们需要一个状态变量进行判断。因为我们需要出现一个感染者的情况，因此对于这种情况，我们直接记录感染者的位置。对于未出现感染者的情况，我们将状态设置为 -1，对于出现多个感染者的情况，我们将状态设置为 -2：
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
n = len(graph)
visited = [False] * n
def dfs(node):
visited[node] = True
nonlocal size, status
size += 1
if status != -2 and node in initial:
if status == -1:
status = node
else:
status = -2
for idx, conn in enumerate(graph[node]):
if conn and not visited[idx]:
dfs(idx)
for node in initial:
if visited[node]:
continue
size = 0
status = -1
dfs(node)接下来就是在 dfs 后进行处理啦，如果此时 status>0，说明出现了我们需要的节点，我们可以判断本次经过块数是否是最大的，如果是的话就更新 max_size 和答案。当然还有一种情况是 size==max_size，此时判断这个节点的 id 是否更小，更小的话就更新答案。
在最后返回答案或 initial 中的最小值即可。
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
st = set(initial)
n = len(graph)
visited = [False] * n
def dfs(node):
visited[node] = True
nonlocal size, status
size += 1
if status != -2 and node in st:
if status == -1:
status = node
else:
status = -2
for idx, conn in enumerate(graph[node]):
if conn and not visited[idx]:
dfs(idx)
max_size = 0
ans = -1
for node in initial:
if visited[node]:
continue
size = 0
status = -1
dfs(node)
if status >= 0:
if size > max_size or (size == max_size and status < ans):
max_size = size
ans = status
return ans if ans >= 0 else min(initial)