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``,其中元素互不相同。 自建示例 -------- 删除感染源并切断整条传播链: .. code-block:: text 输入: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。 感染结果并列时返回较小编号: .. code-block:: text 输入:graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [2,1] 输出:1 解释:三个节点互不连接。删除 1 或 2 后都只剩另一个感染节点,因此返回编号较小的 1。