0928. Minimize Malware Spread II

题目信息

题号:

0928

难度:

Hard

主题:

无向图、感染传播、删除节点

原题:

LeetCode 0928

重点:

从图中彻底删除一个初始感染节点及其所有关联边,再让其他感染源传播;最终感染数相同时返回编号最小的删除节点

题目重述

给定无向图的邻接矩阵 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。