class Solution {
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
}
};
924. 尽量减少恶意软件的传播
给出了一个由 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.lengthn == graph[i].length2 <= n <= 300graph[i][j] == 0 或 1.graph[i][j] == graph[j][i]graph[i][i] == 11 <= initial.length <= n0 <= initial[i] <= n - 1initial 中所有整数均不重复原站题解
rust 解法, 执行用时: 20 ms, 内存消耗: 3.1 MB, 提交时间: 2024-04-16 09:36:02
impl Solution {
pub fn min_malware_spread(graph: Vec<Vec<i32>>, initial: Vec<i32>) -> i32 {
let n = graph.len();
let mut vis = vec![false; n];
let mut is_initial = vec![false; n];
for &x in &initial {
is_initial[x as usize] = true;
}
let mut ans = -1;
let mut max_size = 0;
for &x in &initial {
if vis[x as usize] {
continue;
}
let mut node_id = -1;
let mut size = 0;
Self::dfs(x as usize, &graph, &mut vis, &is_initial, &mut node_id, &mut size);
if node_id >= 0 && (size > max_size || size == max_size && node_id < ans) {
ans = node_id;
max_size = size;
}
}
if ans < 0 { *initial.iter().min().unwrap() } else { ans }
}
fn dfs(x: usize, graph: &Vec<Vec<i32>>, vis: &mut Vec<bool>, is_initial: &Vec<bool>, node_id: &mut i32, size: &mut i32) {
vis[x] = true;
*size += 1;
// 按照状态机更新 node_id
if *node_id != -2 && is_initial[x] {
*node_id = if *node_id == -1 { x as i32 } else { -2 };
}
for (y, &conn) in graph[x].iter().enumerate() {
if conn == 1 && !vis[y] {
Self::dfs(y, graph, vis, is_initial, node_id, size);
}
}
}
}
javascript 解法, 执行用时: 85 ms, 内存消耗: 57.8 MB, 提交时间: 2024-04-16 09:29:23
/**
* @param {number[][]} graph
* @param {number[]} initial
* @return {number}
*/
var minMalwareSpread = function(graph, initial) {
const st = new Set(initial);
const vis = Array(graph.length).fill(false);
let nodeId, size;
function dfs(x) {
vis[x] = true;
size++;
// 按照状态机更新 nodeId
if (nodeId !== -2 && st.has(x)) {
nodeId = nodeId === -1 ? x : -2;
}
for (let y = 0; y < graph[x].length; y++) {
if (graph[x][y] === 1 && !vis[y]) {
dfs(y);
}
}
}
let ans = -1;
let max_size = 0;
for (const x of initial) {
if (vis[x]) {
continue;
}
nodeId = -1;
size = 0;
dfs(x);
if (nodeId >= 0 && (size > max_size || size === max_size && nodeId < ans)) {
ans = nodeId;
max_size = size;
}
}
return ans < 0 ? Math.min(...initial) : ans;
};
cpp 解法, 执行用时: 196 ms, 内存消耗: 63.7 MB, 提交时间: 2023-10-10 14:50:26
class DFU {
public:
vector<int> parent;
vector<int> rank;
vector<int> size;
DFU(int n): parent(n), rank(n), size(n, 1) {
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x) {
if (x != parent[x]) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void merge(int x, int y) {
int rx = find(x);
int ry = find(y);
if (rx != ry) {
if (rank[rx] < rank[ry]) swap(rx, ry);
parent[ry] = rx;
size[rx] += size[ry];
size[ry] = 0;
if (rank[rx] == rank[ry]) rank[rx] += 1;
}
}
};
class Solution {
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int n = graph.size();
sort(initial.begin(), initial.end());
// 合并 连通点
DFU ds(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (graph[i][j] == 1) ds.merge(i, j);
}
}
// 计算每个连通分量的感染个数
vector<int> infect(n);
for (auto& i : initial) {
infect[ds.find(i)]++;
}
int maxM = INT_MIN;
int idx = initial[0];
for (auto& i : initial) {
int ri = ds.find(i);
// 连通分量的感染节点如果多于 1， 最后该连通分量肯定会全部感染
if (infect[ri] != 1) continue;
// 连通分量的感染节点为 1， 去掉该节点后，最后该连通分量全部正常
if (ds.size[ri] > maxM) {
maxM = ds.size[ri];
idx = i;
}
}
return idx;
}
};
golang 解法, 执行用时: 152 ms, 内存消耗: 7.2 MB, 提交时间: 2023-10-10 14:48:31
const MaxInt = int(^uint(0) >> 1)
func minMalwareSpread(graph [][]int, initial []int) int {
colors := make([]int, len(graph))
for i := 0; i < len(graph); i++ {
colors[i] = -1
}
c := 0
for node := 0; node < len(graph); node++ {
if colors[node] == -1 {
dfs(graph, colors, node, c)
c++
}
}
size := make([]int, c)
for _, color := range colors {
size[color]++
}
colorCnt := make([]int, c)
for _, node := range initial {
colorCnt[colors[node]]++
}
ans := MaxInt
for _, node := range initial {
color := colors[node]
if colorCnt[color] == 1 {
if ans == MaxInt {
ans = node
} else if size[color] > size[colors[ans]] {
ans = node
} else if size[color] == size[colors[ans]] && node < ans {
ans = node
}
}
}
if ans == MaxInt {
for _, node := range initial {
ans = min(ans, node)
}
}
return ans
}
func dfs(graph [][]int, colors []int, node, color int) {
colors[node] = color
for nei := 0; nei < len(graph); nei++ {
if graph[node][nei] == 1 && colors[nei] == -1 {
dfs(graph, colors, nei, color)
}
}
}
func min(x, y int) int { if x < y { return x }; return y }
golang 解法, 执行用时: 156 ms, 内存消耗: 7 MB, 提交时间: 2023-10-10 14:47:49
type UnionFindSet struct {
Parents []int //记录每个节点的上级
Size []int // 记录以当前结点为顶点的连通分量里面的节点有多少个（只有自己的话，值为1）
}
func (u *UnionFindSet) Init(size int) {
u.Parents = make([]int, size)
u.Size = make([]int, size)
for i := 0; i < size; i++ {
u.Parents[i] = i
u.Size[i] = 1
}
}
func (u *UnionFindSet) Find(node int) int {
if u.Parents[node] == node {
return node
}
root := u.Find(u.Parents[node])
u.Parents[node] = root
return root
}
func (u *UnionFindSet) Union(node1 int, node2 int) {
root1 := u.Find(node1)
root2 := u.Find(node2)
if root1 == root2 {
return
}
if root1 < root2 {
u.Parents[root1] = root2
u.Size[root2] += u.Size[root1] // 以root2为最顶层结点的连通分量的个数要叠加上root1的
}
}
func minMalwareSpread(graph [][]int, initial []int) int {
// 初始化并查集
u := &UnionFindSet{}
u.Init(len(graph))
// 根据graph进行连通，生成连通分量，并记录连通分量的大小
for i := 0; i < len(graph); i++ {
for j := 0; j < len(graph[i]); j++ {
if graph[i][j] == 1 {
u.Union(i,j)
}
}
}
// 查找目标，统计每个感染节点的颜色情况
// 先对Init进行排序
sort.Ints(initial)
count := make(map[int]int,0)
for i := 0; i < len(initial); i++ {
count[u.Find(initial[i])]++
}
// 1. 如果有唯一颜色的，就选择其中连通分量最大的
ans := -1
ansSize := -1
root := 0
for i := 0; i < len(initial); i++ {
// 是唯一颜色的
root = u.Find(initial[i])
if count[root] == 1 && (ans == -1 || ansSize < u.Size[root]) {
ans = initial[i]
ansSize = u.Size[root]
}
}
// 2. 如果没有唯一颜色的节点，就选择下标最小的
if ans == -1 {
ans = initial[0]
}
return ans
}
python3 解法, 执行用时: 184 ms, 内存消耗: 19.6 MB, 提交时间: 2023-10-10 14:47:15
class Solution:
# bfs
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
n = len(graph)
adj = defaultdict(list)
for i in range(n):
for j in range(n):
if graph[i][j]:
adj[i].append(j)
def bfs(start: int) -> List[int]:
rec = [0] * n
rec[start] = 1
q = deque([start])
while q:
cur = q.popleft()
for nxt in adj[cur]:
if not rec[nxt]:
rec[nxt] = 1
q.append(nxt)
return rec
res = [bfs(i) for i in initial]
cnt = [0]*n
for row in res:
for j in range(n):
cnt[j] += row[j]
f_min = inf
ans = n
for i, item in enumerate(res):
tmp = 0
for j in range(n):
tmp += cnt[j] > item[j]
if tmp < f_min:
f_min = tmp
ans = initial[i]
elif tmp == f_min:
ans = min(ans, initial[i])
return ans
python3 解法, 执行用时: 108 ms, 内存消耗: 27.5 MB, 提交时间: 2023-10-10 14:46:22
class Solution:
# dfs
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
# 1. Color each component.
# colors[node] = the color of this node.
N = len(graph)
colors = {}
c = 0
def dfs(node, color):
colors[node] = color
for nei, adj in enumerate(graph[node]):
if adj and nei not in colors:
dfs(nei, color)
for node in range(N):
if node not in colors:
dfs(node, c)
c += 1
# 2. Size of each color.
# size[color] = number of occurrences of this color.
size = collections.Counter(colors.values())
# 3. Find unique colors.
color_count = collections.Counter()
for node in initial:
color_count[colors[node]] += 1
# 4. Answer
ans = float('inf')
for x in initial:
c = colors[x]
if color_count[c] == 1:
if ans == float('inf'):
ans = x
elif size[c] > size[colors[ans]]:
ans = x
elif size[c] == size[colors[ans]] and x < ans:
ans = x
return ans if ans < float('inf') else min(initial)
python3 解法, 执行用时: 168 ms, 内存消耗: 19.5 MB, 提交时间: 2023-10-10 14:45:40
class DSU:
def __init__(self, N):
self.p = [i for i in range(N)]
self.sz = [1 for i in range(N)]
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, x, y):
xr = self.find(x)
yr = self.find(y)
self.p[xr] = yr
self.sz[yr] += self.sz[xr]
def size(self, x):
return self.sz[self.find(x)]
class Solution:
# 基于并查集
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
dsu = DSU(len(graph))
for j, row in enumerate(graph):
for i in range(j):
if row[i]:
dsu.union(i, j)
count = collections.Counter(dsu.find(u) for u in initial)
ans = (-1, min(initial))
for node in initial:
root = dsu.find(node)
if count[root] == 1: # unique color
if dsu.size(root) > ans[0]:
ans = dsu.size(root), node
elif dsu.size(root) == ans[0] and node < ans[1]:
ans = dsu.size(root), node
return ans[1]
java 解法, 执行用时: 6 ms, 内存消耗: 57.3 MB, 提交时间: 2023-10-10 14:44:01
class Solution {
// 基于并查集，找出图中所有的连通分量
public int minMalwareSpread(int[][] graph, int[] initial) {
int N = graph.length;
DSU dsu = new DSU(N);
for (int i = 0; i < N; ++i)
for (int j = i+1; j < N; ++j)
if (graph[i][j] == 1)
dsu.union(i, j);
int[] count = new int[N];
for (int node: initial)
count[dsu.find(node)]++;
int ans = -1, ansSize = -1;
for (int node: initial) {
int root = dsu.find(node);
if (count[root] == 1) { // unique color
int rootSize = dsu.size(root);
if (rootSize > ansSize) {
ansSize = rootSize;
ans = node;
} else if (rootSize == ansSize && node < ans) {
ansSize = rootSize;
ans = node;
}
}
}
if (ans == -1) {
ans = Integer.MAX_VALUE;
for (int node: initial)
ans = Math.min(ans, node);
}
return ans;
}
}
class DSU {
int[] p, sz;
DSU(int N) {
p = new int[N];
for (int x = 0; x < N; ++x)
p[x] = x;
sz = new int[N];
Arrays.fill(sz, 1);
}
public int find(int x) {
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
public void union(int x, int y) {
int xr = find(x);
int yr = find(y);
p[xr] = yr;
sz[yr] += sz[xr];
}
public int size(int x) {
return sz[find(x)];
}
}
java 解法, 执行用时: 6 ms, 内存消耗: 57.2 MB, 提交时间: 2023-10-10 14:43:10
class Solution {
// dfs
public int minMalwareSpread(int[][] graph, int[] initial) {
// 1. Color each component.
// colors[node] = the color of this node.
int N = graph.length;
int[] colors = new int[N];
Arrays.fill(colors, -1);
int C = 0;
for (int node = 0; node < N; ++node)
if (colors[node] == -1)
dfs(graph, colors, node, C++);
// 2. 每种颜色的数量
int[] size = new int[C];
for (int color: colors)
size[color]++;
// 3. 查找唯一的颜色
int[] colorCount = new int[C];
for (int node: initial)
colorCount[colors[node]]++;
// 4. 获得答案
int ans = Integer.MAX_VALUE;
for (int node: initial) {
int c = colors[node];
if (colorCount[c] == 1) {
if (ans == Integer.MAX_VALUE)
ans = node;
else if (size[c] > size[colors[ans]])
ans = node;
else if (size[c] == size[colors[ans]] && node < ans)
ans = node;
}
}
if (ans == Integer.MAX_VALUE)
for (int node: initial)
ans = Math.min(ans, node);
return ans;
}
public void dfs(int[][] graph, int[] colors, int node, int color) {
colors[node] = color;
for (int nei = 0; nei < graph.length; ++nei)
if (graph[node][nei] == 1 && colors[nei] == -1)
dfs(graph, colors, nei, color);
}
}