# LeetCode: 928. 尽量减少恶意软件的传播 II¶

## 1、题目描述¶

(这个问题与 尽量减少恶意软件的传播 是一样的，不同之处用粗体表示。)

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



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



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



• 1 < graph.length = graph[0].length <= 300
• 0 <= graph[i][j] == graph[j][i] <= 1
• graph[i][i] = 1
• 1 <= initial.length < graph.length
• 0 <= initial[i] < graph.length

## 2、解题思路¶

• 并查集

• 首先将所有的不包含病毒节点的其他连接计算出来
• 然后一次判断每个病毒节点连接的集合，找出唯一与当前病毒节点相连接的集合，并将集合中的元素数量计算出来，元素数量就是移除该节点的收益值
• 需要判断某些集合是不是同时与其他集合相连接，这时候需要统计集合出现的次数，超过一次的表示同时与多个病毒节点相连接，该集合不做计算
class DFU:
def __init__(self, length):
self.data = list(range(length))
self.size = [1] * length

def find(self, x):
if self.data[x] != x:
self.data[x] = self.find(self.data[x])
return self.data[x]

def union(self, x, y):
xp = self.find(x)
yp = self.find(y)
if xp != yp:
self.size[xp] += self.size[yp]
self.data[yp] = xp

def count(self):
res = 0
for index, i in enumerate(self.data):
if index == i:
res += 1
return res

class Solution:
def minMalwareSpread(self, graph: [[int]], initial: [int]) -> int:
from collections import defaultdict, Counter
length = len(graph)
safe = [x for x in range(length) if x not in initial]

d = DFU(length)

for i in safe:
for j in safe:
if graph[i][j]:
d.union(i, j)

virus_collection = defaultdict(set)
count = Counter()
for node in initial:
temp_collection = set()
for j in safe:
if graph[node][j]:

for i in temp_collection:
count[i] += 1
virus_collection[node] = temp_collection

ans = (-1, min(initial))

for node in initial:
score = 0
for collection in virus_collection[node]:
if count[collection] == 1:
score += d.size[collection]

if score > ans[0] or score == ans[0] and node < ans[1]:
ans = score, node
return ans[1]