928. 最小化恶意软件的传播 II

Hard

题目描述

给你一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示，在节点网络中，只有当 graph[i][j] = 1 时，节点 i 和节点 j 之间有边连接。

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

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

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

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

示例 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

提示：

n == graph.length
n == graph[i].length
2 <= n <= 300
graph[i][j] 为 0 或 1
graph[i][j] == graph[j][i]
graph[i][i] == 1
1 <= initial.length < n
0 <= initial[i] <= n - 1
initial 中所有整数互不相同

解题思路

这道题的核心思想是分析移除每个感染节点对恶意软件传播的影响。

基本思路：

首先找到所有连通分量，这可以通过DFS/BFS或并查集实现
对于每个连通分量，统计其中有多少个初始感染节点
关键洞察：只有当一个连通分量中恰好只有一个初始感染节点时，移除这个节点才能阻止整个连通分量被感染

详细分析：

如果一个连通分量中有0个初始感染节点，那么它不会被感染
如果一个连通分量中有2个或更多初始感染节点，移除其中任何一个都无法阻止传播
如果一个连通分量中恰好有1个初始感染节点，移除它可以拯救整个连通分量

算法步骤：

使用并查集或DFS找到所有连通分量
对每个连通分量统计：大小和其中的初始感染节点数量
找出那些恰好包含一个初始感染节点的连通分量
在这些候选节点中，选择能拯救最多节点的那个
如果多个节点拯救的节点数相同，选择索引最小的

时间复杂度O(n²)，空间复杂度O(n)。

代码实现

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();
        vector<int> parent(n);
        vector<int> size(n, 1);
        
        // 初始化并查集
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        function<int(int)> find = [&](int x) {
            return parent[x] == x ? x : parent[x] = find(parent[x]);
        };
        
        auto unite = [&](int x, int y) {
            x = find(x);
            y = find(y);
            if (x != y) {
                parent[y] = x;
                size[x] += size[y];
            }
        };
        
        // 构建连通分量
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (graph[i][j]) {
                    unite(i, j);
                }
            }
        }
        
        // 统计每个连通分量中的初始感染节点数
        unordered_map<int, vector<int>> componentToInitial;
        for (int node : initial) {
            componentToInitial[find(node)].push_back(node);
        }
        
        int maxSave = 0;
        int result = *min_element(initial.begin(), initial.end());
        
        // 检查每个初始感染节点
        for (int node : initial) {
            int root = find(node);
            // 只有当连通分量中恰好有一个初始感染节点时，移除它才有意义
            if (componentToInitial[root].size() == 1) {
                int saved = size[root];
                if (saved > maxSave || (saved == maxSave && node < result)) {
                    maxSave = saved;
                    result = node;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        parent = list(range(n))
        size = [1] * n
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def unite(x, y):
            px, py = find(x), find(y)
            if px != py:
                parent[py] = px
                size[px] += size[py]
        
        # 构建连通分量
        for i in range(n):
            for j in range(i + 1, n):
                if graph[i][j]:
                    unite(i, j)
        
        # 统计每个连通分量中的初始感染节点数
        from collections import defaultdict
        component_to_initial = defaultdict(list)
        for node in initial:
            component_to_initial[find(node)].append(node)
        
        max_save = 0
        result = min(initial)
        
        # 检查每个初始感染节点
        for node in initial:
            root = find(node)
            # 只有当连通分量中恰好有一个初始感染节点时，移除它才有意义
            if len(component_to_initial[root]) == 1:
                saved = size[root]
                if saved > max_save or (saved == max_save and node < result):
                    max_save = saved
                    result = node
        
        return result

public class Solution {
    public int MinMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.Length;
        int[] parent = new int[n];
        int[] size = new int[n];
        
        // 初始化并查集
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        
        int Find(int x) {
            return parent[x] == x ? x : parent[x] = Find(parent[x]);
        }
        
        void Unite(int x, int y) {
            x = Find(x);
            y = Find(y);
            if (x != y) {
                parent[y] = x;
                size[x] += size[y];
            }
        }
        
        // 构建连通分量
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (graph[i][j] == 1) {
                    Unite(i, j);
                }
            }
        }
        
        // 统计每个连通分量中的初始感染节点数
        var componentToInitial = new Dictionary<int, List<int>>();
        foreach (int node in initial) {
            int root = Find(node);
            if (!componentToInitial.ContainsKey(root)) {
                componentToInitial[root] = new List<int>();
            }
            componentToInitial[root].Add(node);
        }
        
        int maxSave = 0;
        int result = initial.Min();
        
        // 检查每个初始感染节点
        foreach (int node in initial) {
            int root = Find(node);
            // 只有当连通分量中恰好有一个初始感染节点时，移除它才有意义
            if (componentToInitial[root].Count == 1) {
                int saved = size[root];
                if (saved > maxSave || (saved == maxSave && node < result)) {
                    maxSave = saved;
                    result = node;
                }
            }
        }
        
        return result;
    }
}

var minMalwareSpread = function(graph, initial) {
    const n = graph.length;
    const parent = Array.from({length: n}, (_, i) => i);
    const size = new Array(n).fill(1);
    
    function find(x) {
        return parent[x]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	时间复杂度	空间复杂度
并查集解法	O(n²·α(n))	O(n)

其中 α(n) 是反阿克曼函数，在实际应用中可以视为常数。时间复杂度主要来自于遍历图的邻接矩阵。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析