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