【Day 77 】2024-01-31 - 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

[snmyj]

class UnionFind {
public:
    UnionFind(int len) {
        parent.resize(len, -1);
    }
    int findRootParent(int p) {
        if (parent[p] == -1 || p == parent[p]) return p;
        return findRootParent(parent[p]);
    }
    void unionConn(int p1, int p2) {
        int p1Root = findRootParent(p1);
        int p2Root = findRootParent(p2);
        if (p1Root != p2Root) {

            parent[p1Root] = p2Root;
        }
    }

private:
    vector<int> parent;
};

class Solution {
public:
    static bool cmp(vector<int>& l, vector<int>& r) {
        return l[1] > r[1] || (l[1] == r[1] && l[0] < r[0]);
    }

    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int rowLen = graph.size();
        if (rowLen == 0) {
            return 0;
        }
        int colLen = graph[0].size();
        if (colLen == 0) {
            return 0;
        }
        UnionFind uf(rowLen);
        for (int row = 0; row < rowLen; ++row) {
            for (int col = 0; col < colLen; ++col) {
                if (graph[row][col] == 1) {
                    uf.unionConn(row, col);
                }
            }
        }
        unordered_map<int, int> rootNum;
        for (int i = 0; i < rowLen; ++i) {
            int rootP = uf.findRootParent(i);
            ++rootNum[rootP];
        }
        vector<int> color(rowLen);
        vector<int> groupNum(rowLen, -1);
        for (int i = 0; i < rowLen; ++i) {
            int rootP = uf.findRootParent(i);
            color[i] = rootP;
            groupNum[i] = rootNum[rootP];
        }
        map<int, int> nodeNumPerColor;
        for (int i = 0; i < initial.size(); ++i) {
            ++nodeNumPerColor[color[initial[i]]];
        }
        vector<vector<int>> ans;
        for (int num: initial) {
            if (nodeNumPerColor[color[num]] == 1) {               
                ans.push_back({num, groupNum[num]});
                continue;
            }
            ans.push_back({num, 0});
        }
        sort(ans.begin(), ans.end(), cmp);
        if (!ans.empty()) {
            return ans.at(0).at(0);
        }
        return 0;
    }
};

[adfvcdxv]

/**

• @param {number[][]} graph
• @param {number[]} initial

• @return {number} */ var minMalwareSpread = function (graph, initial) { let map = new Map(); let N = graph.length; for (let i = 0; i < graph.length; i++) { for (let j = i + 1; j < graph.length; j++) { if (graph[i][j] === 1) { let connects = map.get(i) || []; connects.push(j); map.set(i, connects);

          connects = map.get(j) || [];
          connects.push(i);
          map.set(j, connects);
      }
  }

  }

  let result = Infinity; let ansNode; initial.sort((a, b) => a - b); for (let i = 0; i < initial.length; i++) { let val = initial.splice(i, 1)[0]; let ans = count(new Set(initial), initial.concat([]), val); if (ans < result) { result = ans; ansNode = val; } initial.splice(i, 0, val); } return ansNode;

  function count(visited, stack, val) { while (stack.length > 0) { let node = stack.shift(); let next = map.get(node); if (!next) continue; for (let nn of next) { //与减少恶意软件传播I唯一的区别就是这个条件nn!=val若没这个条件就是I的答案了 if (!visited.has(nn) && nn != val) { visited.add(nn); stack.push(nn); } } } return visited.size; } };

[RealDuxy]

from collections import defaultdict

class UnionFind: def init(self, n): self.root = [i for i in range(n)] self.size = [1]*n self.part = n

def find(self, x):
    if x != self.root[x]:
        # 在查询的时候合并到顺带直接根节点
        root_x = self.find(self.root[x])
        self.root[x] = root_x
        return root_x
    return x

def union(self, x, y):
    root_x = self.find(x)
    root_y = self.find(y)
    if root_x == root_y:
        return
    if self.size[root_x] >= self.size[root_y]:
        root_x, root_y = root_y, root_x
    self.root[root_x] = root_y
    self.size[root_y] += self.size[root_x]
    # 将非根节点的秩赋0
    self.size[root_x] = 0
    self.part -= 1
    return

def is_connected(self, x, y):
    return self.find(x) == self.find(y)

def get_root_part(self):
    # 获取每个根节点对应的组
    part = defaultdict(list)
    n = len(self.root)
    for i in range(n):
        part[self.find(i)].append(i)
    return part

def get_root_size(self):
    # 获取每个根节点对应的组大小
    size = defaultdict(int)
    n = len(self.root)
    for i in range(n):
        size[self.find(i)] = self.size[self.find(i)]
    return size

class Solution: def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int: n = len(graph) uf = UnionFind(n) for i in range(n): for j in range(i+1, n): if graph[i][j]: uf.union(i, j) add = -1 ans = -1 virus = set(initial) part = uf.get_root_part() for k in part: cur = 0 node = -1 for i in part[k]: if i in virus: cur += 1 node = i if cur == 1: if len(part[k]) > add: add = len(part[k]) ans = node elif len(part[k]) == add and node < ans: ans = node return ans if ans != -1 else min(initial)