【Day 77 】2023-05-01 - 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 Solution {
public:
  int minMalwareSpread(vector<vector<int>> &graph, vector<int> &initial) {

    int n = graph.size();
    int p[n], size[n];
    function<int(int)> find = [&](int x) {
        if (p[x] != x)p[x] = find(p[x]);
        return p[x];
    };
    function<void(int, int)> unite = [&](int a, int b) {
        a = find(a), b = find(b);
        if (a == b)return;
        if (size[a] < size[b])swap(a, b);
        p[b] = a, size[a] += size[b];
    };
    for (int i = 0; i < n; i++) {
        p[i] = i, size[i] = 1;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (graph[i][j])unite(i, j);
        }
    }
    int cnt[n];
    memset(cnt, 0, sizeof cnt);
    for (int e: initial)cnt[e]++;   
    int curSize = 0, idx = -1;
    for (int e: initial) {
        int rt = find(e);
        if (cnt[rt] == 1) {         
            if (curSize < size[rt])curSize = size[rt], idx = e;
            else if (curSize == size[rt] && e < idx)idx = e;
        }
    }
    if (idx == -1) {
        idx = INT_MAX;
        for (int e: initial)
            if (e < idx)idx = e;
    }

    return idx;
}

};

[RestlessBreeze]

code

class UF
{
public:
    vector<int> parent;
    vector<int> weight;
    int count;

    UF(int N)
    {
        for (int i = 0; i < N; i++)
        {
            parent.push_back(i);
            weight.push_back(1);
        }
        count = N;
    }

    int find(int i)
    {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]); 
    }

    void Union(int i, int j)
    {
        int parentI = find(i);
        int parentJ = find(j);
        if (parentI != parentJ)
        {
            if (weight[parentI] <= weight[parentJ])
            {
                parent[parentI] = parentJ;
                weight[parentJ] += weight[parentI];
                weight[parentI] = 0;
            }
            else
            {
                parent[parentJ] = parentI;
                weight[parentI] += weight[parentJ];
                weight[parentJ] = 0;
            }
            count--;
        }
    }
};

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();
        UF uf(n);
        for (int i = 0; i < graph.size(); i++)
        {
            for (int j = i + 1; j < graph[0].size(); j++)
            {
                if (graph[i][j] == 1)
                    uf.Union(i, j);
            }
        }

        vector<int> record(n, 0);
        for (int i = 0; i < initial.size(); i++)
        {
            record[uf.find(initial[i])]++;
        }

        sort(initial.begin(), initial.end());
        int maxnum = -1;
        int res = -1;
        for (int i = 0; i < initial.size(); i++)
        {
            if (record[uf.find(initial[i])] == 1)
            {
                if (uf.weight[uf.find(initial[i])] > maxnum)
                {
                    maxnum = uf.weight[uf.find(initial[i])];
                    res = initial[i];
                }
                else if (uf.weight[uf.find(initial[i])] > maxnum && initial[i] < res)
                {
                    res = initial[i];
                }
            }
        }

        if (res == -1)
            res = initial[0];
        return res;

    }
};

[Abby-xu]

抄答案

class Solution: def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int: n, fa = len(grid), list(range(len(grid))) def find(x): if fa[x]!=x: fa[x] = find(fa[x]) return fa[x] for i in range(n): for j in range(i+1, n): if grid[i][j]: fa[find(j)] = find(i) cnter = Counter(find(i) for i in range(n)) cnter_m = Counter(find(i) for i in mal)
return min([(-cnter[find(i)], i) for i in mal if cnter_m[find(i)]==1] or [(0, min(mal))])[1]

[Diana21170648]

思路

dfs，并查集也可做

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        def dfs(i):
            nodes.add(i)
            for j in range(len(graph[i])):
                if graph[i][j] and j not in nodes:
                    dfs(j)
        rank,initial=collections.defaultdict(list),set(initial)
        for node in sorted(initial):
            nodes=set()
            dfs(node)
            if nodes&initial=={node}:
                rank[len(nodes)].append(node)
        return rank[max(rank)][0] if rank else min(initial)

**复杂度分析**
- 时间复杂度：O(N^2)，其中 N 为数组长度。
- 空间复杂度：O(N)

[FireHaoSky]

思路：并查集

代码：python

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)

复杂度分析：

"""
时间复杂度：O(n^2)
空间复杂度：O(n)
"""

[harperz24]

class DSU:
    def __init__(self, n):
        self.root = list(range(n))
        self.rank = [1] * n
        self.size = [1] * n

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

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        if xr == yr:
            return
        xrank, yrank = self.rank[xr], self.rank[yr]
        if xrank >= yrank:
            self.root[yr] = xr
            self.size[xr] += self.size[yr]
            rank_up = 1 if xrank == yrank else 0
            self.rank[xr] += rank_up 
        else:
            self.root[xr] = yr
            self.size[yr] += self.size[xr]

    def get_size(self, x):
        return self.size[self.find(x)]

class Solution(object):
    def minMalwareSpread(self, graph, initial):
        n = len(graph)
        dsu = DSU(n)

        for i in range(n):
            for j in range(i + 1, n):
                if graph[i][j] == 1:
                    dsu.union(i, j)

        count = collections.Counter(dsu.find(u) for u in initial)
        res = (-1, min(initial))
        for node in initial:
            root = dsu.find(node)
            if count[root] == 1:  # unique color
                if dsu.get_size(root) > res[0]:
                    res = dsu.get_size(root), node
                elif dsu.get_size(root) == res[0] and node < res[1]:
                    res = dsu.get_size(root), node

        return res[1]

[zhangyu1131]

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        // 先并查集找出有几个连通分量
        parent_map_.clear();
        int n = graph.size();
        for (int i = 0; i < n; ++i)
        {
            parent_map_[i] = i;
        }
        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                if (graph[i][j] == 1)
                {
                    union_map(i, j);
                }
            }
        }

        // 求每个联通分量的个数
        map<int, int> size_map;
        for (auto& pair : parent_map_)
        {
            size_map[pair.second]++;
        }

        // 处理initial
        int m = initial.size();
        vector<int> visited(n, 0);
        for(int i = 0; i < m; ++i)
        {
            int parent = find(initial[i]);
            visited[parent]++;
        }
        int max_num = -1;
        int ans = -1;
        for (int i = 0; i < m; ++i)
        {
            int parent = find(initial[i]);
            if (visited[parent] == 1)
            {
                if (size_map[parent] > max_num)
                {
                    max_num = size_map[parent];
                    ans = initial[i];
                }
                else if (size_map[parent] == max_num && initial[i] < ans)
                {
                    ans = initial[i];
                }
               //cout << "i:" << i << ",max_num:" << max_num << endl;
            }
        }
        if (ans == -1)
        {
            ans = INT_MAX;
            for (auto num : initial)
            {
                ans = std::min(ans, num);
            }
        }

        return ans;
    }

// 继续练习写并查集
private:
    int find(int node)
    {
        if (node != parent_map_[node])
        {
            parent_map_[node] = find(parent_map_[node]);
        }
        return parent_map_[node];
    }

    void union_map(int node1, int node2)
    {
        if (find(node1) == find(node2))
        {
            return;
        }

        int parent_1 = find(node1);
        int parent_2 = find(node2);
        if (parent_1 < parent_2)
        {
            parent_map_[parent_2] = parent_1;
            // for(auto& pair : parent_map_)
            // {
            //     if (pair.second == parent_2)
            //     {
            //         pair.second = parent_1;
            //     }
            // }
        }
        else
        {
            parent_map_[parent_1] = parent_2;
            // for(auto& pair : parent_map_)
            // {
            //     if (pair.second == parent_1)
            //     {
            //         pair.second = parent_2;
            //     }
            // }
        }
    }
private:
    map<int, int> parent_map_;// 并查集的代表map
};

[Size-of]

/**
 * @param {number[][]} graph
 * @param {number[]} initial
 * @return {number}
 */
 var minMalwareSpread = function(graph, initial) {
    const n = graph.length;
    const p = new Array(n).fill(-1);
    const size = new Array(n).fill(1);
    const st = Array.from(new Array(n),()=>new Array(n).fill(false));
    let min = n;
    let idx = -1;

    var find = x =>{
      if(p[x]!==x)p[x] = find(p[x]);
      return p[x];
    }

    var merge = (x,y)=>{
      if(find(x)===find(y))return;
      size[find(y)] += size[find(x)];
      p[find(x)] = find(y);
      st[x][y] = st[y][x] =true;
    }

    for(let i=0;i<n;i++) p[i]=i;

    for(let i=0;i<n;i++)
      for(let j=0;j<n;j++)
          if(graph[i][j]){
              if(i===j || st[i][j])continue;
              merge(i,j);
          }

    initial.sort((a,b)=> a-b);

    for(let e of initial){
        const set = new Set();
        let res = 0;
        for(let i of initial){
            if(i===e)continue;
            else{
                let ri  = find(i);
                if(!set.has(ri)){
                    set.add(ri);
                    res += size[ri];
                }
            }
        }
        if(res<min){
            min = res;
            idx = e;
        }
    }
    return idx===-1 ? initial[0] : idx;
};

[Jetery]

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size(), m = initial.size();
        int res = INT_MAX, ans = -1;

        for (int j = 0; j < m; j++) {
            queue<int> q;
            vector<bool> vis(n, false);
            int tot = 0;

            for (int i = 0; i < m; i++)
                if (initial[i] != initial[j]) {
                    q.push(initial[i]);
                    vis[initial[i]] = true;
                    tot++;
                }

            while (!q.empty()) {
                int cur = q.front();
                q.pop();
                for (int i = 0; i < n; i++)
                    if (graph[cur][i] == 1 && !vis[i]) {
                        vis[i] = true;
                        q.push(i);
                        tot++;
                    }
            }

            if (res > tot) {
                res = tot;
                ans = initial[j];
            } else if (res == tot && ans > initial[j]) {
                ans = initial[j];
            }
        }

        return ans;
    }
};

[JasonQiu]

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        initial = set(initial)
        group = set()
        groups = defaultdict(list)

        def dfs(node):
            group.add(node)
            for next_node in range(len(graph[node])):
                if graph[node][next_node] and next_node not in group:
                    dfs(next_node)

        for n in sorted(initial):
            dfs(n)
            if group & initial == {n}:
                print(group, initial, n)
                groups[len(group)].append(n)
            group = set()

        return groups[max(groups)][0] if groups else min(initial)

Time: O(n^2) Space: O(n)

[aoxiangw]

class Solution(object):
    def minMalwareSpread(self, graph, initial):
        """
        :type graph: List[List[int]]
        :type initial: List[int]
        :rtype: int
        """
        def find(x):
            while x != uf[x]:
                uf[x] = uf[uf[x]]
                x = uf[x]
            return uf[x]

        def union(x, y):
            x_root = find(x)
            y_root = find(y)
            uf[x_root] = y_root

        uf = [i for i in range(len(graph))]
        for i in range(len(graph)):
            for j in range(i+1, len(graph)):
                if graph[i][j]:
                    union(i, j)

        lookup, dup = {}, {}
        for i in range(len(graph)):
            root = find(i)
            lookup[root] = lookup.get(root, 0) + 1
            if i in initial:
                dup[root] = dup.get(root, -1) + 1

        component_sizes_of_initial = [lookup[find(ini)]-dup[find(ini)] for ini in initial]
        max_component_size = max(component_sizes_of_initial)

        res = []
        for i in range(len(initial)):
            if component_sizes_of_initial[i] == max_component_size:
                res.append(initial[i])
        return min(res)

[bookyue]

TC: O(n)
SC: O(n)

    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        int[] colors = new int[n];
        Arrays.fill(colors, -1);
        int color = 0;

        for (int i = 0; i < n; i++) {
            if (colors[i] != -1) continue;

            dfs(graph, colors, i, color);
            color++;
        }

        int[] size = new int[color];
        for (int c : colors) size[c]++;

        int[] cnt = new int[color];
        for (int i : initial) cnt[colors[i]]++;

        Arrays.sort(initial);
        int ans = initial[0];
        int max = Integer.MIN_VALUE;
        for (int i : initial) {
            int c = colors[i];
            if (cnt[c] != 1) continue;

            if (size[c] > max) {
                max = size[c];
                ans = i;
            }
        }

        return ans;
    }

    private void dfs(int[][] graph, int[] colors, int cur, int color) {
        colors[cur] = color;
        for (int nei = 0; nei < graph.length; nei++) {
            if (graph[cur][nei] == 1 && colors[nei] == -1)
                dfs(graph, colors, nei, color);
        }
    }

[Lydia61]

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

思路

图解

代码

class Solution:
    def minMalwareSpread(self, graph: list[list[int]], initial: list[int]) -> int:
        n = len(graph)
        p = list(range(n))
        s = [1] * n
        m = [0] * n
        o = [0] * n

        def find(index: int) -> int:
            if p[index] != index:
                p[index] = find(p[index])
            return p[index]

        for i, row in enumerate(graph):
            for j, val in enumerate(row):
                if val:
                    pi, pj = find(i), find(j)
                    if pi == pj:
                        continue
                    p[pi] = pj
                    s[pj] += s[pi]

        mi = 300
        for v in initial:
            pv = find(v)
            m[pv] += 1
            o[pv] = v
            mi = min(mi, v)

        ans = -1
        size = 0
        for i, v in enumerate(m):
            if v == 1:
                if s[i] > size:
                    ans = o[i]
                    size = s[i]
                elif s[i] == size and o[i] < ans:
                    ans = o[i]

        if ans == -1:
            return mi
        return ans

[NorthSeacoder]

/**
 * @param {number[][]} graph
 * @param {number[]} initial
 * @return {number}
 */
var minMalwareSpread = function (graph, initial) {
    //initial 中移除一个节点使得与 initial连通数最少;=>找到 initial 中联通最多的
    const uf = new UF()
    for (let i = 0; i < graph.length; i++) {
        for (let j = 0; j < graph[0].length; j++) {
            if (graph[i][j] === 1) {
                uf.add(i);
                uf.add(j);
                uf.union(i, j)
            }
        }

    };
    let counts = graph.reduce((acc, cur, index) => {
        let root = uf.find(index);
        if (!acc[root]) {
            acc[root] = 0;
        }
        acc[root]++;
        return acc;
    }, {});
    initial.sort((a, b) => a - b);
    let res = initial[0], max = -Infinity;
    initial.map(point => uf.find(point)).forEach((item, index, arr) => {
        if (arr.indexOf(item) === arr.lastIndexOf(item)) {
            const nums = uf.findSize(item);
            if (nums > max) {
                res = initial[index];
                max = nums
            }
        }
    })
    return res
};

class UF {
    constructor() {
        this.root = {};
        this.nums = {};//key=>所属集合(root[node]),value:数量
    };

    add(node) {
        if (!this.root[node] && this.root[node] !== 0) {
            this.root[node] = node;
            this.nums[node] = 1
        }
    }

    find(node) {
        if (this.root[node] === node) return node;
        return this.root[node] = this.find(this.root[node])
    }

    contac(a, b) {
        return this.find(a) === this.find(b)
    }

    union(a, b) {
        let parentA = this.find(a);
        let parentB = this.find(b);
        if (parentA !== parentB) {
            this.root[parentA] = parentB;
            this.nums[parentB] += this.nums[parentA];
        }
    }

    findSize(root) {
        return this.nums[root]
    }
}

[huizsh]

class Solution {

public int minMalwareSpread(int[][] graph, int[] initial) {
    int n = graph.length;
    UF uf = new UF(n);
    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            if(graph[i][j]==1) {
                uf.union(i,j);
            }
        }
    }
    int[] count = new int[n];
    for(int node: initial) {
        count[uf.find(node)]++;
    }
    int ans=-1, ansSize=-1;
    for(int node: initial) {
        int root = uf.find(node);
        if(count[root]==1) {
            int currSize = uf.getSize(root);
            if(currSize>ansSize) {
                ansSize=currSize;
                ans=node;
            }
            else if(currSize == ansSize && node < ans) {
                ans=node;
            }
        }
    }
    if(ans==-1) {
        ans=n+1;
        for(int node: initial) {
            ans = Math.min(node,ans);
        }
    }
    return ans;

}
class UF {
    int[] parent;
    int[] size;

    public UF(int n) {
        parent = new int[n];
        size = new int[n];
        for(int i=0;i<n;i++) {
            parent[i]=i;
            size[i]=1;
        }
    }
    public int find(int x) {
        while(parent[x]!=x) {
            parent[x]=parent[parent[x]];
            x=parent[x];
        }
        return parent[x];
    }
    public int getSize(int x) {
        return size[find(x)];
    }
    public void union(int x, int y) {
        int xroot = find(x);
        int yroot = find(y);
        if(xroot!=yroot) {
            if(size[xroot]>size[yroot]) {
                parent[yroot]=xroot;
                size[xroot]+=size[yroot];
            }
            else {
                parent[xroot]=yroot;
                size[yroot]+=size[xroot];
            }
        }

    }

}

}

[kangliqi1]

class Solution {

public int minMalwareSpread(int[][] graph, int[] initial) {
    int n = graph.length;
    UF uf = new UF(n);
    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            if(graph[i][j]==1) {
                uf.union(i,j);
            }
        }
    }
    int[] count = new int[n];
    for(int node: initial) {
        count[uf.find(node)]++;
    }
    int ans=-1, ansSize=-1;
    for(int node: initial) {
        int root = uf.find(node);
        if(count[root]==1) {
            int currSize = uf.getSize(root);
            if(currSize>ansSize) {
                ansSize=currSize;
                ans=node;
            }
            else if(currSize == ansSize && node < ans) {
                ans=node;
            }
        }
    }
    if(ans==-1) {
        ans=n+1;
        for(int node: initial) {
            ans = Math.min(node,ans);
        }
    }
    return ans;

}
class UF {
    int[] parent;
    int[] size;

    public UF(int n) {
        parent = new int[n];
        size = new int[n];
        for(int i=0;i<n;i++) {
            parent[i]=i;
            size[i]=1;
        }
    }
    public int find(int x) {
        while(parent[x]!=x) {
            parent[x]=parent[parent[x]];
            x=parent[x];
        }
        return parent[x];
    }
    public int getSize(int x) {
        return size[find(x)];
    }
    public void union(int x, int y) {
        int xroot = find(x);
        int yroot = find(y);
        if(xroot!=yroot) {
            if(size[xroot]>size[yroot]) {
                parent[yroot]=xroot;
                size[xroot]+=size[yroot];
            }
            else {
                parent[xroot]=yroot;
                size[yroot]+=size[xroot];
            }
        }

    }

}

}

[joemonkeylee]

思路

未做出 记录一种做法

代码

 int[] fa;
    public int MinMalwareSpread(int[][] graph, int[] initial)
    {
        int n = graph.Length;
        fa = new int[n];
        for (int i = 0; i < n; i++) fa[i] = i;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if(graph[i][j] == 1) fa[Find(i)] = Find(j); //并查集
            }
        }
        int[] nexts = new int[n];
        for (int i = 0; i < n; i++) nexts[Find(i)]++; //计算每个集合的数量
        Dictionary<int, int> initFaCnt = new Dictionary<int, int>();
        for (int i = 0; i < initial.Length; i++)
        {
            int v = initial[i];
            if (!initFaCnt.ContainsKey(Find(v))) initFaCnt[Find(v)] = 0;
            initFaCnt[Find(v)]++; //统计初始值里属于同一个集合的数量
        }
        Array.Sort(initial, (A, B) =>
        {
            int cntA = initFaCnt[Find(A)];
            int cntB = initFaCnt[Find(B)];
            if(cntA == 1 && cntB > 1) return -1;
            if(cntA > 1 && cntB == 1) return 1; //查看AB是否是各自集合的唯一元素
            if(cntA == 1 && cntB == 1)
            {
                //只有AB都是各自集合唯一的元素时，才会比较两个集合的size
                int ret = nexts[Find(B)] - nexts[Find(A)];
                if(ret != 0) return ret;
            }
            return A - B;
        });
        return initial[0];
    }

    private int Find(int x)
    {
        return fa[x] == x ? x : (fa[x] = Find(fa[x]));
    }

[X1AOX1A]

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]

[lp1506947671]

class Solution:
    def minMalwareSpread(self, graph, initial):
        def dfs(i):
            nodes.add(i)
            for j in range(len(graph[i])):
                if graph[i][j] and j not in nodes:
                    dfs(j)
        rank, initial = collections.defaultdict(list), set(initial)
        for node in sorted(initial):
            nodes = set()
            dfs(node)
            if nodes & initial == {node}:
                rank[len(nodes)].append(node)
        return rank[max(rank)][0] if rank else min(initial)

复杂度分析

令 d 为矩阵 M 的大小，e 为 initial 长度。

• 时间复杂度：由于使用了排序，因此排序需要时间为 eloge。而 dfs 部分，由于每个点呗访问最多一次，因此时间为 O(d^2)
• 空间复杂度：我们使用了 colors 和 counts，因此空间复杂度为 O(d)

[kofzhang]

思路

并查集

代码

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        res = []
        nodes = [-1] * len(graph)
        def union(a ,b ,nodes):
            a = find(a ,nodes)
            b = find(b ,nodes)
            if a == b:
                return a
            elif a < b:
                nodes[b] = a
            else:
                nodes[a] = b

        def find(a ,nodes):
            t = a
            while nodes[t]>=0:
                t = nodes[t]
            while t!= a:
                nodes[a], a = t, nodes[a]
            return t

        for i in range(len(graph)):
            for j in range(i + 1, len(graph)):
                if graph[i][j] == 1:
                    union(i, j, nodes)

        for e in initial:
            s = set()
            for i in initial:
                if i != e:
                    s.add(find(i, nodes))
            r = len(s)
            for i in nodes:
                if i in s:
                    r += 1
            res.append((r, e))

        res.sort(key=lambda x: (x[0], x[1]))
        return res[0][1]