割点，LeetCode 928. 尽量减少恶意软件的传播 II

一、题目

1、题目描述

给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示。在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

我们可以从 initial 中删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。

请返回移除后能够使 M(initial) 最小化的节点。如果有多个节点满足条件，返回索引 最小的节点 。

2、接口描述

python3

​

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:

cpp

​

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {

    }
};

3、原题链接

928. 尽量减少恶意软件的传播 II

二、解题报告

1、思路分析

我们考虑暴力做法，枚举每个非法结点删除的情况下，图中的最终非法节点数，然后维护答案

这样的做法是O(n^2 * m)，m为非法结点的个数

我们考虑优化：

删除非法结点x前，x所在连通块一定都会被感染，删除后，是否能够产生不存在非法节点的连通块？

我们类比Tarjan求割点的做法

我们仍然对图进行dfs，只不过不允许普通结点越过非法节点进行访问，同时记录此连通块访问到的非法节点的数目

如果非法结点数目大于1，那么删除任意的非法节点也不能产生非感染连通块

如果非法结点数目等于1，那么可以产生，将该连通块贡献累加到访问的非法节点上

我们维护答案并返回即可

2、复杂度

时间复杂度：O(n^2) 空间复杂度：O(n^2)

3、代码详解

python3

​

class Solution:
    def minMalwareSpread(self, g: List[List[int]], initial: List[int]) -> int:
        n = len(g)
        vis = [False] * n
        nums = set(initial)
        def dfs(x: int) -> None:
            vis[x] = True
            nonlocal idx, sz
            sz += 1
            for y, st in enumerate(g[x]):
                if not st:
                    continue
                if y in nums:
                    if idx != -2 and idx != y:
                        idx = y if idx == -1 else -2 
                elif not vis[y]:
                    dfs(y)
        cnt = Counter()
        for i, st in enumerate(vis):
            if st or i in nums:
                continue
            idx = -1
            sz = 0
            dfs(i)
            if idx >= 0:
                cnt[idx] += sz
        return min((-sz, idx) for idx, sz in cnt.items())[1] if cnt else min(initial)

cpp

​

class Solution {
public:
static constexpr int N = 305;
bool vis[N];
int cnt[N];
    int minMalwareSpread(vector<vector<int>>& g, vector<int>& initial) {
        memset(vis, 0, sizeof vis);
        memset(cnt, 0, sizeof cnt);
        int n = g.size(), sz, idx;
        set<int> nums(initial.begin(), initial.end());
        function<void(int)> dfs = [&](int x){
            sz ++, vis[x] = 1;
            for(int y = 0; y < n; y++){
                if(!g[x][y]) continue;
                if(nums.count(y)){
                    if(idx != -2 && idx != y)
                        idx = ~idx ? -2 : y;
                }
                else if(!vis[y]){
                    dfs(y);
                }
            }
        };
        int ret = -1, ma = 0;
        for(int x = 0; x < n; x++){
            if(vis[x] || nums.count(x)) continue;
            idx = -1, sz = 0;
            dfs(x);
            if(idx >= 0){
                cnt[idx] += sz;
                if(cnt[idx] > ma || cnt[idx] == ma && idx < ret)
                    ret = idx, ma = cnt[idx]; 
            }
        }
        return ret < 0 ? *nums.begin() : ret;
    }
};