LeetCode 0924.尽量减少恶意软件的传播：连通块染色（以BFS为例）

【LetMeFly】924.尽量减少恶意软件的传播：连通块染色（以BFS为例）

力扣题目链接：https://leetcode.cn/problems/minimize-malware-spread/

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

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

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

如果从 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 中所有整数均不重复

解题方法：连通块染色（以BFS为例）

解题思路

我们将所有相互连通的节点（称为连通块）染成相同的颜色，不同连通块染成不同的颜色，并记录下每个连通块的大小。

这样，对于intial中的节点t：

• 如果存在另一节点i和t同色，则初始时移除该节点无意义；
• 否则，初始时移除节点t的话，和t同色的节点都将幸免。

具体方法

对于连通块染色：

• 使用数组color[i]代表节点i的颜色，初始值全为0（代表无色）；
• 使用数组color2size[i]代表颜色为i的节点的个数。

遍历每个节点，若该节点未被染色，则发现新的连通块：

将该节点染成一个新的颜色，创建一个队列并将该节点入队。

队列非空时，出队一个节点，并遍历这个节点的所有相邻节点。

若某相邻节点未被染色，则将其染成相同的颜色，并更新color2size的大小。

时空复杂度

• 时间复杂度$O(len(graph{)}^2)$
• 空间复杂度$O(len(graph))$

AC代码

C++

class Solution {
private:
    int canDesc(int t, vector<int>& initial, vector<int>& color, vector<int>& color2size) {
        for (int i : initial) {
            if (color[i] == color[t] && i != t) {
                return 0;
            }
        }
        return color2size[color[t]];
    }
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int cntColor = 0;
        vector<int> color(graph.size());
        vector<int> color2size(graph.size() + 1);
        for (int i = 0; i < graph.size(); i++) {  // begin from each node
            if (color[i]) {
                continue;
            }
            cntColor++;
            queue<int> q;
            q.push(i);
            color[i] = cntColor;
            color2size[cntColor]++;
            while (q.size()) {
                int thisNode = q.front();
                q.pop();
                for (int j = 0; j < graph.size(); j++) {
                    if (graph[thisNode][j] && !color[j]) {
                        q.push(j);
                        color[j] = cntColor;
                        color2size[cntColor]++;
                    }
                }
            }
        }
        int ans, maxDesc = -1;
        sort(initial.begin(), initial.end());
        for (int t : initial) {
            int thisDesc = canDesc(t, initial, color, color2size);
            if (thisDesc > maxDesc) {
                maxDesc = thisDesc;
                ans = t;
            }
        }
        return ans;
    }
};

Python

# from typing import List

class Solution:
    def canDesc(self, t, initial, color, color2cnt) -> int:
        for i in initial:
            if color[i] == color[t] and i != t:
                return 0
        return color2cnt[color[t]]
    
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        color = [0] * len(graph)
        color2cnt = [0] * (len(graph) + 1)
        cntColor = 0
        for i in range(len(graph)):
            if color[i]:
                continue
            cntColor += 1
            color[i] = cntColor
            color2cnt[cntColor] = 1
            q = [i]
            while q:
                thisNode = q.pop()
                for j in range(len(graph)):
                    if graph[thisNode][j] and not color[j]:
                        color[j] = cntColor
                        color2cnt[cntColor] += 1
                        q.append(j)
        ans, maxDesc = 0, -1
        initial.sort()
        for t in initial:
            thisDesc = self.canDesc(t, initial, color, color2cnt)
            if thisDesc > maxDesc:
                maxDesc = thisDesc
                ans = t
        return ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/137815658