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

链接：928.尽量减少恶意软件的传播II
难度：Hard
标签：深度优先搜索、广度优先搜索、并查集、图、数组、哈希表
简介：我们可以从 initial 中删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。请返回移除后能够使 M(initial) 最小化的节点。如果有多个节点满足条件，返回索引 最小的节点 。

题解 1 - python

• 编辑时间：2024-04-17
• 执行用时：601ms
• 内存消耗：19.4MB
• 编程语言：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)
        def get(ignore_index: int) -> int:
            uf = UnionFind(n)
            res = 0
            for i in range(n):
                for j in range(n):
                    if i == ignore_index or j == ignore_index: continue
                    if graph[i][j]: uf.uni(i, j)
            used = set()
            for i in initial:
                if i != ignore_index:
                    parent = uf.find(i)
                    if parent not in used:
                        used.add(parent)
                        res += uf.size(parent)
            return (res, ignore_index)
        return min(get(i) for i in initial)[1]