0924. Minimize Malware Spread¶
题目信息¶
- 题号:
0924
- 难度:
Hard
- 主题:
无向图、感染传播、初始节点选择
- 原题:
- 重点:
只从初始感染集合中移除一个节点,图和该节点本身仍然存在;传播结束感染数相同时返回编号最小的被移除节点
题目重述¶
给定无向图的邻接矩阵 graph 和互不相同的初始感染节点数组 initial。感染会沿边不断传播:只要一个节点与任意已感染节点相连,它最终也会被感染,直到状态不再变化。
必须从 initial 中移除恰好一个节点,使它不再作为初始感染源,然后重新执行传播。该节点并未从图中删除,仍可能被其他感染节点感染并继续传播。请选择使最终感染节点总数最少的移除对象;若多个选择得到相同最小值,返回编号最小者。
2 <= graph.length <= 300,矩阵对称且 graph[i][i] == 1;1 <= initial.length <= graph.length。
自建示例¶
优先挽救更大的连通分量:
输入:graph = [[1,1,0,0,0],[1,1,1,0,0],[0,1,1,0,0],[0,0,0,1,1],[0,0,0,1,1]], initial = [0,3]
输出:0
解释:节点 0、1、2 构成大小为 3 的分量,节点 3、4 构成大小为 2 的分量。移除初始感染源 0 可使前三个节点全部不被感染,比移除 3 挽救的节点更多。
最终感染数并列时返回较小编号:
输入:graph = [[1,0],[0,1]], initial = [1,0]
输出:0
解释:两个节点互不连通。移除任一初始感染源后都只剩一个感染节点,因此按规则返回编号较小的 0。