924. 最小化恶意软件传播

Hard

题目描述

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

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

假设 M(initial) 是在恶意软件停止传播之后，整个网络中被恶意软件感染的节点数。我们将从 initial 中恰好移除一个节点。

返回移除哪一个节点，能够最小化 M(initial)。如果移除多个节点都能够最小化 M(initial)，就返回索引最小的节点。

注意，如果一个节点从 initial 的感染节点列表中移除，它可能仍然因为恶意软件传播而受到感染。

示例 1：

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

示例 2：

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

示例 3：

输入：graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
输出：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或并查集找到图中的所有连通分量。在同一个连通分量内，如果有任何一个初始感染节点，整个连通分量都会被感染。
关键观察：移除一个初始感染节点只有在以下情况下才有意义：
- 该节点是其所在连通分量中唯一的初始感染节点
- 如果连通分量中有多个初始感染节点，移除其中一个不会影响该连通分量的感染状态
最优策略：
- 对于每个连通分量，统计其中的初始感染节点数量和总节点数量
- 如果连通分量只有一个初始感染节点，移除它可以拯救整个连通分量
- 在所有候选节点中，选择能拯救最多节点的那个
- 如果拯救节点数相同，选择索引最小的

算法步骤：

使用DFS找到所有连通分量
对每个连通分量统计初始感染节点数和总节点数
计算移除每个初始感染节点能拯救的节点数
返回能拯救最多节点的初始感染节点（索引最小优先）

代码实现

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();
        vector<bool> visited(n, false);
        vector<int> component(n, -1);
        vector<vector<int>> components;
        
        // 找到所有连通分量
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                vector<int> comp;
                dfs(graph, i, visited, comp);
                for (int node : comp) {
                    component[node] = components.size();
                }
                components.push_back(comp);
            }
        }
        
        // 统计每个连通分量中的初始感染节点数
        vector<int> infectedCount(components.size(), 0);
        set<int> initialSet(initial.begin(), initial.end());
        
        for (int node : initial) {
            infectedCount[component[node]]++;
        }
        
        int maxSaved = -1;
        int result = *min_element(initial.begin(), initial.end());
        
        // 对每个初始感染节点计算移除后能拯救的节点数
        for (int node : initial) {
            int comp = component[node];
            int saved = 0;
            
            // 只有当该节点是连通分量中唯一的初始感染节点时才有意义
            if (infectedCount[comp] == 1) {
                saved = components[comp].size();
            }
            
            if (saved > maxSaved || (saved == maxSaved && node < result)) {
                maxSaved = saved;
                result = node;
            }
        }
        
        return result;
    }
    
private:
    void dfs(vector<vector<int>>& graph, int node, vector<bool>& visited, vector<int>& component) {
        visited[node] = true;
        component.push_back(node);
        
        for (int i = 0; i < graph.size(); i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                dfs(graph, i, visited, component);
            }
        }
    }
};

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        visited = [False] * n
        component = [-1] * n
        components = []
        
        # 找到所有连通分量
        for i in range(n):
            if not visited[i]:
                comp = []
                self.dfs(graph, i, visited, comp)
                for node in comp:
                    component[node] = len(components)
                components.append(comp)
        
        # 统计每个连通分量中的初始感染节点数
        infected_count = [0] * len(components)
        initial_set = set(initial)
        
        for node in initial:
            infected_count[component[node]] += 1
        
        max_saved = -1
        result = min(initial)
        
        # 对每个初始感染节点计算移除后能拯救的节点数
        for node in initial:
            comp = component[node]
            saved = 0
            
            # 只有当该节点是连通分量中唯一的初始感染节点时才有意义
            if infected_count[comp] == 1:
                saved = len(components[comp])
            
            if saved > max_saved or (saved == max_saved and node < result):
                max_saved = saved
                result = node
        
        return result
    
    def dfs(self, graph, node, visited, component):
        visited[node] = True
        component.append(node)
        
        for i in range(len(graph)):
            if graph[node][i] == 1 and not visited[i]:
                self.dfs(graph, i, visited, component)

public class Solution {
    public int MinMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.Length;
        bool[] visited = new bool[n];
        int[] component = new int[n];
        List<List<int>> components = new List<List<int>>();
        
        // 初始化component数组
        for (int i = 0; i < n; i++) {
            component[i] = -1;
        }
        
        // 找到所有连通分量
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                List<int> comp = new List<int>();
                DFS(graph, i, visited, comp);
                foreach (int node in comp) {
                    component[node] = components.Count;
                }
                components.Add(comp);
            }
        }
        
        // 统计每个连通分量中的初始感染节点数
        int[] infectedCount = new int[components.Count];
        HashSet<int> initialSet = new HashSet<int>(initial);
        
        foreach (int node in initial) {
            infectedCount[component[node]]++;
        }
        
        int maxSaved = -1;
        int result = initial.Min();
        
        // 对每个初始感染节点计算移除后能拯救的节点数
        foreach (int node in initial) {
            int comp = component[node];
            int saved = 0;
            
            // 只有当该节点是连通分量中唯一的初始感染节点时才有意义
            if (infectedCount[comp] == 1) {
                saved = components[comp].Count;
            }
            
            if (saved > maxSaved || (saved == maxSaved && node < result)) {
                maxSaved = saved;
                result = node;
            }
        }
        
        return result;
    }
    
    private void DFS(int[][] graph, int node, bool[] visited, List<int> component) {
        visited[node] = true;
        component.Add(node);
        
        for (int i = 0; i < graph.Length; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                DFS(graph, i, visited, component);
            }
        }
    }
}

var minMalwareSpread = function(graph, initial) {
    const n = graph.length;
    const visited = new Array(n).fill(false);
    const component = new Array(n).fill(-1);
    const components = [];
    
    // 找到所有连通分量
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            const comp = [];
            dfs(graph, i, visited, comp);
            for (const node of comp) {
                component[node] = components.length;
            }
            components.push(comp);
        }
    }
    
    // 统计每个连通分量中的初始感染节点数
    const infectedCount = new Array(components.length).fill(0);
    const initialSet = new Set(initial);
    
    for (const node of initial) {
        infectedCount[component[node]]++;
    }
    
    let maxSaved = -1;
    let result = Math.min(...initial);
    
    // 对每个初始感染节点计算移除后能拯救的节点数
    for (const node of initial) {
        const comp = component[node];
        let saved = 0;
        
        // 只有当该节点是连通分量中唯一的初始感染节点时才有意义
        if (infectedCount[comp]

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

复杂度分析

复杂度类型	值
时间复杂度	O(n²)
空间复杂度	O(n)

时间复杂度分析：

DFS遍历图需要O(n²)时间，因为需要检查所有边
统计连通分量和计算结果需要O(n)时间
总时间复杂度为O(n²)

空间复杂度分析：

visited数组、component数组各需要O(n)空间
components列表最多存储n个节点，需要O(n)空间
DFS递归栈最深为O(n)
总空间复杂度为O(n)

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析