924.尽量减少恶意软件的传播

链接：924.尽量减少恶意软件的传播
难度：Hard
标签：深度优先搜索、广度优先搜索、并查集、图、数组、哈希表
简介：如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。

题解 1 - python

• 编辑时间：2024-04-16
• 执行用时：163ms
• 内存消耗：19.87MB
• 编程语言：python
• 解法介绍：并查集。

class UnionFind:
    def __init__(self, n) -> None:
        self.n = n
        self.data = [i for i in range(0, n)]
        self.sizes = [1] * n
        self.cnt = n
    def size(self, v: int) -> int:
        return self.sizes[self.find(v)]
    def find(self, v: int) -> int:
        if self.data[v] != v:
            self.data[v] = self.find(self.data[v])
        return self.data[v]
    def uni(self, v1: int, v2: int):
        p1 = self.find(v1)
        p2 = self.find(v2)
        if p1 != p2:
            self.sizes[p1] += self.sizes[p2]
            self.cnt -= self.sizes[p2]
            self.data[p2] = p1
    def same(self, v1: int, v2: int):
        return self.find(v1) == self.find(v2)
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        uf = UnionFind(n)
        resIndex = -1
        resVal = inf
        for i in range(n):
            for j in range(n):
                if graph[i][j]:
                    uf.uni(i, j)
        for i in initial:
            sum = 0
            used = set()
            for j in initial:
                if i != j:
                    parent = uf.find(j)
                    if parent not in used:
                        used.add(parent)
                        sum += uf.size(parent)
            if sum < resVal or (sum == resVal and i < resIndex):
                resVal = sum
                resIndex = i
        return resIndex