LeetCode 928. Minimize Malware Spread II - AcWing

LeetCode 928. Minimize Malware Spread II - AcWing

(这道题目类似于LeetCode 924. Minimize Malware Spread，不同之处用已加粗)。

在一个网络中，节点i和节点j相邻，当且仅当graph[i][j] = 1。

一些节点，存于initial中，已经被恶意软件感染。如果两个相邻的节点中，其中一个节点被感染，则另一个节点也会被感染。这种感染方式会持续进行，直到没有新节点被感染为止。

假设M(initial)表示整个网络最终被感染的节点数。

我们可以从整个网络中 完全删掉一个节点，及其关联的所有边 。
请返回删除后，可使M(initial)最小的点。如果答案不唯一，请返回编号最小的点。

注意：

1. 1 < graph.length = graph[0].length <= 300
2. 0 <= graph[i][j] == graph[j][i] <= 1
3. graph[i][i] = 1
4. 1 <= initial.length < graph.length
5. 0 <= initial[i] < graph.length

样例1

输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]  输出：0  

样例2

输入：graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]  输出：1  

样例3

输入：graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]  输出：1  

---

算法

(并查集) $O(n^2)$

首先我们先将所有的病毒节点去掉，然后将所有连通块合并成一个节点。
这是因为一个连通块中的节点，要么全部被感染，要么全部不被感染，所以我们可以将它们当成一个整体来考虑。

然后我们统计一下所有连通块，直接相邻的病毒节点的个数。
对于一个连通块：

• 如果直接相邻的病毒节点的个数为0，则一定不会被感染，忽略之；
• 如果直接相邻的病毒节点的个数为1，则将该病毒节点删除后，整个连通块就可以避免被感染；
• 如果直接相邻的病毒节点的个数大于等于2，则不管删除哪个病毒节点，该连通块都仍会被感染，忽略之；

所以我们只需在所有第二种连通块（直接相邻的病毒节点的个数为1的连通块）中，找出节点个数最多的连通块，与它相邻的病毒节点就是我们要删除的节点；如果有多个连通块节点个数相同，我们找出与之对应的编号最小的病毒节点即可。

时间复杂度分析：

• 合并所有非病毒节点的连通块：$O(n^2)$；
• 统计每个连通块节点的个数：$O(n)$；
• 统计每个连通块连接的病毒节点个数：$O(n^2)$；
• 遍历所有连通块，求需要删除的节点：$O(n)$；

所以总时间复杂度是 $O(n^2)$。

C++ 代码

Read full article from LeetCode 928. Minimize Malware Spread II - AcWing