尽量减少恶意软件的传播

难度: Hard

给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

如果从 initial 中移除某一节点能够最小化 M(initial)，返回该节点。如果有多个节点满足条件，就返回索引最小的节点。

请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

n == graph.length
n == graph[i].length
2 <= n <= 300
graph[i][j] == 0 或 1.
graph[i][j] == graph[j][i]
graph[i][i] == 1
1 <= initial.length <= n
0 <= initial[i] <= n - 1
initial 中所有整数均不重复

Submission

运行时间: 84 ms

内存: 19.4 MB

class UnionFind:
    def __init__(self,graph):
        self.root = [n for n in range(len(graph))]
        self.size = [1]*len(graph)
    
    def find(self,i):
        while(i!=self.root[i]):
            i = self.root[i]
        return self.root[i]
    def Union(self,i,j):
        root1 = self.find(i)
        root2 = self.find(j)
        if root1==root2:
            return
        self.root[root1] = root2
        self.size[root2]+=self.size[root1]
    def getsize(self,i):
        return self.size[i]
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        m = len(graph)
        uf = UnionFind(graph)
        for i in range(m):
            for j in range(i):
                if graph[i][j]:
                    uf.Union(i,j)
        count = Counter(uf.find(x) for x in initial)
        res = [-1,min(initial)]
        for node in initial:
            root = uf.find(node)
            if count[root]==1:
                if uf.getsize(root)>res[0]:
                    res = [uf.getsize(root),node]
                elif uf.getsize(root)==res[0] and node<res[1]:
                    res[1] = node

        return res[1]

Explain

该题解使用了并查集来解决问题。首先根据图构建并查集，将所有连通的节点合并到同一个集合中。然后遍历初始感染节点列表initial，统计每个集合的感染节点数量。如果某个集合只有一个感染节点，就计算删除该节点后能减少感染的节点数，同时更新能减少最多感染节点数的节点索引。最后返回能减少最多感染节点数且索引最小的节点。

时间复杂度: O(n^2 + m)

空间复杂度: O(n + m)

class UnionFind:
    def __init__(self, graph):
        self.root = [n for n in range(len(graph))]  # 初始化节点的根节点为自身
        self.size = [1] * len(graph)  # 初始化每个集合的大小为1
    
    def find(self, i):
        # 查找节点i所在集合的根节点
        while i != self.root[i]:
            i = self.root[i]
        return self.root[i]

    def Union(self, i, j):
        # 合并节点i和节点j所在的集合
        root1 = self.find(i)
        root2 = self.find(j)
        if root1 == root2:
            return
        self.root[root1] = root2
        self.size[root2] += self.size[root1]

    def getsize(self, i):
        # 获取节点i所在集合的大小
        return self.size[i]

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        m = len(graph)
        uf = UnionFind(graph)
        for i in range(m):
            for j in range(i):
                if graph[i][j]:
                    uf.Union(i, j)  # 将所有连通的节点合并到同一个集合
        count = Counter(uf.find(x) for x in initial)  # 统计每个集合的感染节点数量
        res = [-1, min(initial)]  # 初始化结果，第一个元素为最大减少感染节点数，第二个元素为对应的节点索引
        for node in initial:
            root = uf.find(node)
            if count[root] == 1:  # 如果该集合只有一个感染节点
                if uf.getsize(root) > res[0]:  # 如果删除该节点能减少更多感染节点数
                    res = [uf.getsize(root), node]  # 更新结果
                elif uf.getsize(root) == res[0] and node < res[1]:  # 如果减少相同数量的感染节点，选择索引更小的节点
                    res[1] = node
        return res[1]  # 返回能减少最多感染节点数且索引最小的节点

Explore

在并查集中处理多个连通分量时，首先通过遍历图中的每条边来合并节点，将属于同一个连通分量的节点合并到同一个集合中。对于初始感染节点，我们通过遍历这些节点并使用并查集的`find`方法来确定每个节点所属的集合。然后，我们统计每个集合中初始感染节点的数量。即使集合被不同数量的初始感染节点连接，这种方法也能正确地识别并统计每个集合内的感染节点数量，从而在后续步骤中做出相应的处理决策。

题解中的并查集的`Union`方法没有明确实现按秩合并。在题解的实现中，当两个节点合并时，简单地将一个集合的根指向另一个集合的根，并更新大小。这种方法可能导致不平衡的树结构，从而影响操作的效率。按秩合并或路径压缩技术可以显著优化并查集操作的性能，特别是在处理大规模数据时，这两种技术能够保持树的高度较低，从而使查找操作更快。

题解中通过使用`Counter`字典来统计每个集合的感染节点数量，这种方法依赖于并查集的`find`函数来识别每个初始感染节点所属的集合。只要`find`函数能够准确地返回每个节点的根节点，就可以确保每个初始感染节点被正确归类到其所在的集合。因此，计数的准确性主要取决于并查集的正确实现和维护。

如果一个集合中有多个感染节点，删除其中一个感染节点通常不会影响其他节点的感染状态，因为剩余的感染节点仍然可以维持集合内的感染。在这种情况下，删除一个感染节点不会减少集合的总感染节点数，因为集合中仍然存在其他感染源。因此，在有多个感染节点的集合中，选择删除哪个节点应该基于其他标准，如节点的网络位置或节点的重要性。