2023-06-10：给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。

作者：福大大架构师每日一题

2023-06-10
北京
本文字数：6165 字
阅读完需：约 20 分钟

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;}

复制代码

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/191b53315385e2b53e2849545】。

福大大架构师每日一题

关注

公众号：福大大架构师每日一题 2021-02-15 加入

公众号：福大大架构师每日一题

发布

暂无评论

创作场景

2023-06-10：给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示 在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。

主要思路如下：

go 完整代码如下：

rust 完整代码如下：

c++完整代码如下：

c 完整代码如下：

福大大架构师每日一题

评论

2023-06-10：给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。