【Day 77 】2023-08-25 - 924. 尽量减少恶意软件的传播

[azl397985856]

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

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/minimize-malware-spread

前置知识

暂无

题目描述

在节点网络中，只有当 graph[i][j] = 1 时，每个节点 i 能够直接连接到另一个节点 j。

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

假设 M(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

提示：

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

[Diana21170648]

思路

并查集 dfs

代码

class UF: 
    def __init__ (self):
        self.father={}
        self.size={}
    def find(self,x):
        self.father.setdefault(x,x)
        if x !=self.father[x]:
            self.father[x]=self.find(self.father[x])
        return self.father[x]
    def connect(self,x,y):
        fx,fy=self.find(x),self.find(y)
        if self.size.setdefault(fx,1)<self.size.setdefault(fy,1):
            self.father[fx]=fy
            self.size[fy]+=self.size[fx]
        elif fx!=fy:
            self.father[fy]=fx
            self.size[fx] +=self.size[fy]
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        uf=UF()
        for i in range(len(graph)):
            for j in range(i,len(graph)):
                if graph[i][j]:
                    uf.connect(i,j)
        initial.sort()
        max_size,index,fi=0,-1,[]
        cnt=collections.defaultdict(int)
        for init in initial:
            fi.append(uf.find(init))
            cnt[fi[-1]]+=1
        for i in range(len(initial)):
            if cnt[fi[i]]>1:
                continue
            if uf.size[fi[i]]>max_size:
                max_size=uf.size[fi[i]]
                index=initial[i]
        return index if index !=-1 else initial[0]

复杂度分析

• 时间复杂度：O(N*alpha（n）)，其中 N 为矩阵长度长度，n为按秩合并的次数。
• 空间复杂度：O(N)

[Fuku-L]

代码

class Solution {
    int n;

    int[] p;// 并查集root
    int[] s;// 连通节点数量
    int[] m;// 感染节点数量
    int[] o;// 感染来源

    public int minMalwareSpread(int[][] graph, int[] initial) {
        // 初始化并查集
        n = graph.length;
        p = new int[n];
        s = new int[n];
        m = new int[n];
        o = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = i;
            s[i] = 1;
        }
        // 连通节点，记录连通节点数量
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] == 1) {
                    int pi = find(i), pj = find(j);
                    if (pi == pj)
                        continue;
                    int si = s[pi], sj = s[pj];
                    p[pi] = pj;
                    s[pj] = si + sj;
                }
            }
        }
        // 每个连通块的感染数量
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < initial.length; i++) {
            int cur = find(initial[i]);
            m[cur]++;
            o[cur] = initial[i];
            min = Math.min(min, initial[i]);
        }
        int ansi = -1, anss = -1;
        // 只有感染数量是1的有救，这其中联通最大的最值得救，先出先算
        for (int i = 0; i < n; i++) {
            if (m[i] == 1) {
                if (s[i] > anss) {
                    ansi = o[i];
                    anss = s[i];
                } else if (s[i] == anss && o[i] < ansi) {
                    ansi = o[i];// 感染源小的
                }
            }
        }
        return ansi == -1 ? min : ansi;
    }

    private int find(int index) {
        if (p[index] != index) {
            p[index] = find(p[index]);
        }
        return p[index];
    }
}

[Alexno1no2]

# 思路
# 1 两个字典（Java用两个数组更快），一个用于记录每个节点的父节点，一个用于记录每个连通区域的大小。
# 2 寻找待删除节点时，记录每个源病毒（即initial）所在连通区域的父节点
#     如果某一连通区域有两个源病毒，该区域无论如何都会被感染，放弃该区域
#     在所有只有一个源病毒的连通区域中，选择size最大的区域中的源病毒节点
# 3 因为若满足条件的节点有多个，要返回索引最小的节点。先将源病毒索引排序，只有区域size更大才会更新最后要返回的索引index，可以保证返回的是最小索引。

class UnionFind:
    def __init__(self):
        self.father = {}
        self.size = {}

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

    def union(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if self.size.setdefault(fx, 1) < self.size.setdefault(fy, 1):
            self.father[fx] = fy
            self.size[fy] += self.size[fx]
        elif fx != fy:
            self.father[fy] = fx
            self.size[fx] += self.size[fy]

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        uf = UnionFind()

        # 遍历
        for i in range(len(graph)):
            for j in range(i, len(graph)):
                if graph[i][j]:
                    uf.union(i, j)

        # 寻找最优待删除节点
        initial.sort()
        max_size, index, fi = 0, -1, []
        cnt = collections.defaultdict(int)
        for init in initial:
            fi.append(uf.find(init))
            cnt[fi[-1]] += 1
        for i in range(len(initial)):
            if cnt[fi[i]] > 1:
                continue
            if uf.size[fi[i]] > max_size:
                max_size = uf.size[fi[i]]
                index = initial[i]

        return index if index != -1 else initial[0]

[Beanza]

class Solution: def makeConnected(self, n: int, connections: List[List[int]]) -> int: root = [i for i in range(n)]

    def find(p):
        while p != root[p]:
            root[p] = root[root[p]]
            p = root[p]

        return p

    def union(p, q):
        root[find(p)] = find(q)

    have = 0
    for connec in connections:
        a, b = connec
        if find(a) != find(b):
            union(a, b)
        else:
            have += 1

    diff_root = set()
    for i in range(n):
        diff_root.add(find(i))