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

## 1、题目描述¶

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



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



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



• 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
row = len(graph)
d = DFU(row)
for i in range(row):
for j in range(row):
if graph[i][j] == 1:
d.union(i, j)

count = defaultdict(int)
for i in initial:
count[d.find(i)] += 1

ans = (-1, min(initial))
for i in initial:

father = d.find(i)

if count[father] == 1:
if d.size[father] > ans[0] or d.size[father] == ans[0] and i < ans[1]:
ans = d.size[father], i

return ans[1]