0928. Minimize Malware Spread II¶
题目信息¶
- 题号:
0928
- 难度:
Hard
- 主题:
无向图、感染传播、删除节点
- 原题:
- 重点:
从图中彻底删除一个初始感染节点及其所有关联边,再让其他感染源传播;最终感染数相同时返回编号最小的删除节点
题目重述¶
给定无向图的邻接矩阵 graph 和互不相同的初始感染节点数组 initial。感染从所有未被删除的初始节点开始,并沿图中的边传播,直到不能感染新节点。
必须选择 initial 中恰好一个节点,将该节点及它连接的全部边从图中删除,然后执行传播。请返回使剩余图中最终感染节点数量最少的被删除节点编号;若多个选择得到相同最小感染数,返回编号最小者。
2 <= graph.length <= 300,矩阵对称且 graph[i][i] == 1;1 <= initial.length < graph.length,其中元素互不相同。
自建示例¶
删除感染源并切断整条传播链:
输入:graph = [[1,0,1,0],[0,1,0,0],[1,0,1,1],[0,0,1,1]], initial = [0,1]
输出:0
解释:删除节点 0 后,节点 2、3 不再与任何感染源相连,最终只感染节点 1;删除节点 1 后,节点 0 仍会感染 2、3,因此应删除 0。
感染结果并列时返回较小编号:
输入:graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [2,1]
输出:1
解释:三个节点互不连接。删除 1 或 2 后都只剩另一个感染节点,因此返回编号较小的 1。