2023-06-10：给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示

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

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，

且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。

这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

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

我们可以从 initial 中删除一个节点，

并完全移除该节点以及从该节点到任何其他节点的任何连接。

请返回移除后能够使 M(initial) 最小化的节点。

如果有多个节点满足条件，返回索引 最小的节点 。

initial 中每个整数都不同。

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

输入：0。

答案2023-06-10：

主要思路如下：

1.建立并查集，将感染恶意软件的节点标记出来。

2.遍历节点连接，如果两个节点都没有被感染，则在并查集中合并这两个节点。

3.对于initial中的每个节点，遍历其能够直接连接的节点，如果节点未被感染，则将其在并查集中的祖先标记为initial中的该节点，如果该祖先已被标记为其他initial中的节点，则将其标记为-2。

4.统计在同一个initial的所有节点中，连接的总节点数，找出连接数最多的initial节点。

5.返回最小索引的节点。

时间复杂度为$O(n^2)$，其中n是节点数，因为要对每个节点进行遍历和合并操作，最坏情况下需要$O(n^2)$次遍历和合并操作。

空间复杂度为O(n)，其中n是节点数，因为需要使用一个并查集数组来存储节点的父节点，另外还需要使用一个数组来记录每个节点是否被感染和每个initial节点的连接数量。这些数据占用的空间都是O(n)的。

go完整代码如下：

package main

import (
    "fmt"
    "sort"
)

func minMalwareSpread(graph [][]int, initial []int) int {
    n := len(graph)
    virus := make([]bool, n)
    for _, i := range initial {
        virus[i] = true
    }

    uf := NewUnionFind(n)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if graph[i][j] == 1 && !virus[i] && !virus[j] {
                uf.Union(i, j)
            }
        }
    }

    infect := make([]int, n)
    for i := range infect {
        infect[i] = -1
    }
    for _, v := range initial {
        for next := 0; next < n; next++ {
            if v != next && !virus[next] && graph[v][next] == 1 {
                f := uf.Find(next)
                if infect[f] == -1 {
                    infect[f] = v
                } else if infect[f] != -2 && infect[f] != v {
                    infect[f] = -2
                }
            }
        }
    }

    cnt := make([]int, n)
    for i := 0; i < n; i++ {
        if infect[i] >= 0 {
            cnt[infect[i]] += uf.size[i]
        }
    }

    sort.Ints(initial)
    ans := initial[0]
    count := cnt[ans]
    for _, i := range initial {
        if cnt[i] > count {
            ans = i
            count = cnt[i]
        }
    }

    return ans
}

type UnionFind struct {
    father []int
    size   []int
}

func NewUnionFind(n int) *UnionFind {
    father := make([]int, n)
    size := make([]int, n)
    for i := 0; i < n; i++ {
        father[i] = i
        size[i] = 1
    }
    return &UnionFind{father, size}
}

func (uf *UnionFind) Find(i int) int {
    help := make([]int, 0)
    for i != uf.father[i] {
        help = append(help, i)
        i = uf.father[i]
    }
    for _, v := range help {
        uf.father[v] = i
    }
    return i
}

func (uf *UnionFind) Union(i, j int) {
    fi, fj := uf.Find(i), uf.Find(j)
    if fi != fj {
        if uf.size[fi] >= uf.size[fj] {
            uf.father[fj] = fi
            uf.size[fi] += uf.size[fj]
        } else {
            uf.father[fi] = fj
            uf.size[fj] += uf.size[fi]
        }
    }
}

func main() {
    graph := [][]int{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}
    initial := []int{0, 1}

    fmt.Println(minMalwareSpread(graph, initial))
}

rust完整代码如下：

fn main() {
    let graph = vec![vec![1, 1, 0], vec![1, 1, 0], vec![0, 0, 1]];
    let initial = vec![0, 1];

    println!("{}", min_malware_spread(graph, initial));
}

struct UnionFind {
    father: Vec<i32>,
    size: Vec<i32>,
    help: Vec<i32>,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        let mut father = vec![0; n];
        let mut size = vec![0; n];
        let mut help = vec![0; n];
        for i in 0..n {
            father[i] = i as i32;
            size[i] = 1;
        }
        Self { father, size, help }
    }

    fn find(&mut self, mut i: i32) -> i32 {
        let mut hi = 0;
        while i != self.father[i as usize] {
            self.help[hi as usize] = i;
            hi += 1;
            i = self.father[i as usize];
        }
        while hi != 0 {
            hi -= 1;
            self.father[self.help[hi as usize] as usize] = i;
        }
        i
    }

    fn union(&mut self, i: i32, j: i32) {
        let fi = self.find(i);
        let fj = self.find(j);
        if fi != fj {
            if self.size[fi as usize] >= self.size[fj as usize] {
                self.father[fj as usize] = fi;
                self.size[fi as usize] += self.size[fj as usize];
            } else {
                self.father[fi as usize] = fj;
                self.size[fj as usize] += self.size[fi as usize];
            }
        }
    }
}

fn min_malware_spread(graph: Vec<Vec<i32>>, initial: Vec<i32>) -> i32 {
    let mut graph = graph;
    let mut initial = initial;
    let n: usize = graph.len();
    let mut virus = vec![false; n];
    for i in initial.iter() {
        virus[*i as usize] = true;
    }

    let mut uf = UnionFind::new(n);
    for i in 0..n {
        for j in 0..n {
            if graph[i][j] == 1 && !virus[i] && !virus[j] {
                uf.union(i as i32, j as i32);
            }
        }
    }

    let mut infect = vec![-1; n];
    for &v in initial.iter() {
        for next in 0..n {
            if v != next as i32 && !virus[next] && graph[v as usize][next as usize] == 1 {
                let f = uf.find(next as i32);
                if infect[f as usize] == -1 {
                    infect[f as usize] = v;
                } else if infect[f as usize] != -2 && infect[f as usize] != v {
                    infect[f as usize] = -2;
                }
            }
        }
    }

    let mut cnt = vec![0; n];
    for i in 0..n {
        if infect[i] >= 0 {
            cnt[infect[i] as usize] += uf.size[i as usize];
        }
    }

    initial.sort();
    let mut ans = initial[0];
    let mut count = cnt[ans as usize];
    for &i in initial.iter() {
        if cnt[i as usize] > count {
            ans = i;
            count = cnt[i as usize];
        }
    }

    ans
}

c++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class UnionFind {
public:
    vector<int> father;
    vector<int> size;

    // Constructor
    UnionFind(int n) {
        father.resize(n);
        size.resize(n);
        for (int i = 0; i < n; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    // Find operation
    int Find(int i) {
        vector<int> help;
        while (i != father[i]) {
            help.push_back(i);
            i = father[i];
        }
        for (auto v : help) {
            father[v] = i;
        }
        return i;
    }

    // Union operation
    void Union(int i, int j) {
        int fi = Find(i);
        int fj = Find(j);
        if (fi != fj) {
            if (size[fi] >= size[fj]) {
                father[fj] = fi;
                size[fi] += size[fj];
            }
            else {
                father[fi] = fj;
                size[fj] += size[fi];
            }
        }
    }
};

int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
    int n = graph.size();

    vector<bool> virus(n, false);
    for (auto i : initial) {
        virus[i] = true;
    }

    UnionFind uf(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (graph[i][j] == 1 && !virus[i] && !virus[j]) {
                uf.Union(i, j);
            }
        }
    }

    vector<int> infect(n, -1);
    for (auto v : initial) {
        for (int next = 0; next < n; next++) {
            if (v != next && !virus[next] && graph[v][next] == 1) {
                int f = uf.Find(next);
                if (infect[f] == -1) {
                    infect[f] = v;
                }
                else if (infect[f] != -2 && infect[f] != v) {
                    infect[f] = -2;
                }
            }
        }
    }

    vector<int> cnt(n, 0);
    for (int i = 0; i < n; i++) {
        if (infect[i] >= 0) {
            cnt[infect[i]] += uf.size[i];
        }
    }

    sort(initial.begin(), initial.end());
    int ans = initial[0];
    int count = cnt[ans];
    for (auto i : initial) {
        if (cnt[i] > count) {
            ans = i;
            count = cnt[i];
        }
    }

    return ans;
}

int main() {
    vector<vector<int>> graph = { {1, 1, 0}, {1, 1, 0}, {0, 0, 1} };
    vector<int> initial = { 0, 1 };

    cout << minMalwareSpread(graph, initial) << endl;

    return 0;
}

c完整代码如下：

#include <stdio.h>
#include <stdlib.h>

int cmpfunc(const void* a, const void* b);

typedef struct {
    int* father;
    int* size;
} UnionFind;

UnionFind* createUnionFind(int n) {
    UnionFind* uf = (UnionFind*)malloc(sizeof(UnionFind));
    uf->father = (int*)malloc(n * sizeof(int));
    uf->size = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        uf->father[i] = i;
        uf->size[i] = 1;
    }
    return uf;
}

int find(UnionFind* uf, int i) {
    int hi = 0;
    int* help = (int*)malloc(1000 * sizeof(int));
    while (i != uf->father[i]) {
        help[hi] = i;
        hi += 1;
        i = uf->father[i];
    }
    for (int j = 0; j < hi; j++) {
        uf->father[help[j]] = i;
    }
    free(help);
    return i;
}

void unionSet(UnionFind* uf, int i, int j) {
    int fi = find(uf, i);
    int fj = find(uf, j);
    if (fi != fj) {
        if (uf->size[fi] >= uf->size[fj]) {
            uf->father[fj] = fi;
            uf->size[fi] += uf->size[fj];
        }
        else {
            uf->father[fi] = fj;
            uf->size[fj] += uf->size[fi];
        }
    }
}

int minMalwareSpread(int** graph, int graphSize, int* graphColSize, int* initial, int initialSize) {
    int n = graphSize;

    int* virus = (int*)calloc(n, sizeof(int));
    for (int i = 0; i < initialSize; i++) {
        virus[initial[i]] = 1;
    }

    UnionFind* uf = createUnionFind(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (graph[i][j] == 1 && virus[i] == 0 && virus[j] == 0) {
                unionSet(uf, i, j);
            }
        }
    }

    int* infect = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        infect[i] = -1;
    }
    for (int k = 0; k < initialSize; k++) {
        int v = initial[k];
        for (int next = 0; next < n; next++) {
            if (v != next && virus[next] == 0 && graph[v][next] == 1) {
                int f = find(uf, next);
                if (infect[f] == -1) {
                    infect[f] = v;
                }
                else if (infect[f] != -2 && infect[f] != v) {
                    infect[f] = -2;
                }
            }
        }
    }

    int* cnt = (int*)calloc(n, sizeof(int));
    for (int i = 0; i < n; i++) {
        if (infect[i] >= 0) {
            cnt[infect[i]] += uf->size[i];
        }
    }

    int* sortedInitial = (int*)malloc(initialSize * sizeof(int));
    for (int i = 0; i < initialSize; i++) {
        sortedInitial[i] = initial[i];
    }
    qsort(sortedInitial, initialSize, sizeof(int), cmpfunc);

    int ans = sortedInitial[0];
    int count = cnt[ans];
    for (int i = 0; i < initialSize; i++) {
        if (cnt[sortedInitial[i]] > count) {
            ans = sortedInitial[i];
            count = cnt[ans];
        }
    }

    free(virus);
    free(cnt);
    free(sortedInitial);
    free(infect);
    free(uf->father);
    free(uf->size);
    free(uf);

    return ans;
}

int cmpfunc(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int graphSize = 3;
    int graphColSize[] = { 3, 3, 3 };
    int graphData[][3] = { {1, 1, 0}, {1, 1, 0}, {0, 0, 1} };
    int** graph = (int**)malloc(graphSize * sizeof(int*));
    for (int i = 0; i < graphSize; i++) {
        graph[i] = (int*)malloc(graphColSize[i] * sizeof(int));
        for (int j = 0; j < graphColSize[i]; j++) {
            graph[i][j] = graphData[i][j];
        }
    }

    int initial[] = { 0, 1 };
    int initialSize = 2;
    int ans = minMalwareSpread(graph, graphSize, graphColSize, initial, initialSize);
    printf("%d\n", ans);

    for (int i = 0; i < graphSize; i++) {
        free(graph[i]);
    }
    free(graph);

    return 0;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接