TikTok OA 面试真题解析：Minimize Malware Spread（最小化恶意软件传播）

You are given a network of n nodes represented as an n x n adjacency matrix graph, where graph[i][j] == 1 means the two nodes i and j are connected, and a list of nodes initial that are initially infected by malware.

Malware will spread to connected nodes. M(initial) is the final number of nodes infected with malware after the spread finishes.

Remove exactly one node from initial. The removed node still has the same connections, but it is no longer initially infected. It can still be infected later from other nodes.

Return the node whose removal would minimize M(initial). If multiple nodes can be removed to minimize M(initial), return the node with the smallest value.

Example Input:

graph = [[1,1,1,0,0],
         [1,1,0,0,0],
         [1,0,1,0,0],
         [0,0,0,1,1],
         [0,0,0,1,1]]
initial = [1,3]

Example Output:

1

Explanation:

• If remove 1, then M(initial) = 2 (3 and 4 will be infected).
• If remove 3, then M(initial) = 3 (0, 1, and 2 will be infected).
• Return 1.

这道题本质上是图连通分量上的感染扩散问题：先把网络按连通块划分，再分析每个连通块中有多少个初始感染点。只有“某个连通块恰好只有一个初始感染点”时，删除这个点才会真正减少最终感染规模；否则删掉任意一个点都挡不住该连通块继续被感染。实现时通常用并查集或 DFS/BFS 统计每个连通块的大小和初始感染数量，再枚举初始节点，计算它能独占拯救多少节点，最后按“最多减少感染数、若并列取编号最小”返回答案。