题目
最小化恶意软件传播
信息
- 类型：问答
- 难度：⭐⭐⭐
考点
并查集应用,连通分量分析,图论问题建模,优化策略
快速回答
本题要求通过移除一个节点最小化恶意软件传播，核心解决方案如下：
- 使用并查集统计网络连通分量的大小和每个分量中的初始感染节点数
- 计算所有包含感染节点的连通分量大小之和（记为 S）
- 遍历初始感染节点列表：
- 若节点所在连通分量的感染节点数为 1，移除该节点可使整个分量幸免，最终感染节点数为 S - 分量大小
- 否则移除后仅减少 1 个感染节点（自身），最终感染节点数为 S - 1
- 选择使最终感染节点数最小的节点，若相同则取索引最小者
问题背景与建模
给定一个无向图（邻接矩阵表示）和初始感染节点列表，恶意软件在连通分量中传播：若分量中有至少一个感染节点，则整个分量最终都会被感染。移除一个节点会删除其所有边，可能分裂连通分量。目标是通过移除一个节点，最小化最终感染节点数（移除节点不计入感染）。
核心原理
关键观察：移除节点 u 的效果取决于其所在连通分量 C 的特性：
- 当 C 中只有 1 个感染节点（即 u 本身）：移除 u 后，C 分裂的所有子分量都不含感染节点，整个 C 幸免，感染节点减少量为 C 的大小
- 当 C 中有多个感染节点：移除 u 后，其他感染节点仍会导致 C 剩余部分被感染，感染节点仅减少 1（u 本身）
算法实现（Python）
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.size = [1] * n # 分量大小
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry: return
# 按秩合并
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
self.size[rx] += self.size[ry]
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
def minMalwareSpread(graph, initial):
n = len(graph)
uf = UnionFind(n)
# 构建连通分量
for i in range(n):
for j in range(i + 1, n):
if graph[i][j] == 1:
uf.union(i, j)
# 统计各分量感染节点数
comp_infected = [0] * n
for node in initial:
root = uf.find(node)
comp_infected[root] += 1
# 计算 S：所有感染分量的总大小
S = 0
for i in range(n):
if i == uf.find(i) and comp_infected[i] > 0: # 根节点且含感染
S += uf.size[i]
# 寻找最优移除节点
initial.sort()
best_node = initial[0]
min_infected = float('inf')
for u in initial:
root = uf.find(u)
if comp_infected[root] == 1:
infected_after_remove = S - uf.size[root]
else:
infected_after_remove = S - 1
if infected_after_remove < min_infected or \
(infected_after_remove == min_infected and u < best_node):
min_infected = infected_after_remove
best_node = u
return best_node最佳实践
- 并查集优化：路径压缩 + 按秩合并保证接近 O(α(n)) 时间复杂度
- 分量统计：仅通过根节点访问分量信息，避免重复计算
- 提前排序：对 initial 排序便于处理索引最小要求
常见错误
- 错误 1：未区分分量感染节点数，误认为移除任何节点都能拯救整个分量
- 错误 2：重复计算 S（应对每个连通分量只统计一次）
- 错误 3：未处理分量分裂后的传播逻辑，复杂度过高（应利用关键观察避免显式分裂）
- 错误 4：忽略移除节点自身不计入感染节点的规则
扩展知识
- 多节点移除问题：当允许移除 k 个节点时，问题转化为 NP-Hard，需结合贪心/回溯解决（LeetCode 928）
- 动态网络处理：若网络边动态变化，可使用动态并查集（如 Euler Tour Tree）或分治算法
- 传播模型扩展：考虑概率传播、免疫节点等变种模型时需结合蒙特卡洛模拟或马尔可夫决策
