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

文相

2023-06-10：给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示
在节点网络中，只有当 graph[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)的。
package mainimport ("fmt""sort")func minMalwareSpread(graph int, initial int) int {n := len(graph)virus := make(bool, n)for _, i := range initial {virus = true}uf := NewUnionFind(n)for i := 0; i < n; i++ {for j := 0; j < n; j++ {if graph[j] == 1 && !virus && !virus[j] {uf.Union(i, j)}}}infect := make(int, n)for i := range infect {infect = -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 >= 0 {cnt[infect] += uf.size}}sort.Ints(initial)ans := initial[0]count := cnt[ans]for _, i := range initial {if cnt > count {ans = icount = cnt}}return ans}type UnionFind struct {father intsize int}func NewUnionFind(n int) *UnionFind {father := make(int, n)size := make(int, n)for i := 0; i < n; i++ {father = isize = 1}return &UnionFind{father, size}}func (uf *UnionFind) Find(i int) int {help := make(int, 0)for i != uf.father {help = append(help, i)i = uf.father}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] = fiuf.size[fi] += uf.size[fj]} else {uf.father[fi] = fjuf.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))}

在这里插入图片描述
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,size: Vec,help: Vec,}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 as i32;size = 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, initial: Vec) -> 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[j] == 1 && !virus && !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 >= 0 {cnt[infect 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}

在这里插入图片描述
#include #include #include using namespace std;class UnionFind {public:vector father;vector size;// ConstructorUnionFind(int n) {father.resize(n);size.resize(n);for (int i = 0; i < n; i++) {father = i;size = 1;}}// Find operationint Find(int i) {vector help;while (i != father) {help.push_back(i);i = father;}for (auto v : help) {father[v] = i;}return i;}// Union operationvoid 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& graph, vector& initial) {int n = graph.size;vector virus(n, false);for (auto i : initial) {virus = true;}UnionFind uf(n);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (graph[j] == 1 && !virus && !virus[j]) {uf.Union(i, j);}}}vector 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 cnt(n, 0);for (int i = 0; i < n; i++) {if (infect >= 0) {cnt[infect] += uf.size;}}sort(initial.begin, initial.end);int ans = initial[0];int count = cnt[ans];for (auto i : initial) {if (cnt > count) {ans = i;count = cnt;}}return ans;}int main {vector graph = { {1, 1, 0}, {1, 1, 0}, {0, 0, 1} };vector initial = { 0, 1 };cout size = (int*)malloc(n * sizeof(int));for (int i = 0; i < n; i++) {uf->father = i;uf->size = 1;}return uf;}int find(UnionFind* uf, int i) {int hi = 0;int* help = (int*)malloc(1000 * sizeof(int));while (i != uf->father) {help[hi] = i;hi += 1;i = uf->father;}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] = 1;}UnionFind* uf = createUnionFind(n);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (graph[j] == 1 && virus == 0 && virus[j] == 0) {unionSet(uf, i, j);}}}int* infect = (int*)malloc(n * sizeof(int));for (int i = 0; i < n; i++) {infect = -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 >= 0) {cnt[infect] += uf->size;}}int* sortedInitial = (int*)malloc(initialSize * sizeof(int));for (int i = 0; i < initialSize; i++) {sortedInitial = initial;}qsort(sortedInitial, initialSize, sizeof(int), cmpfunc);int ans = sortedInitial[0];int count = cnt[ans];for (int i = 0; i < initialSize; i++) {if (cnt[sortedInitial] > count) {ans = sortedInitial;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 = (int*)malloc(graphColSize * sizeof(int));for (int j = 0; j < graphColSize; j++) {graph[j] = graphData[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);}free(graph);return 0;}

在这里插入图片描述

福大大架构师每日一题java当死，golang当立。最新面试题，涉及golang，rust，mysql，redis，云原生，算法，分布式，网络，操作系统。557篇原创内容
收录于合集 #福大大架构师每日一题
826个
上一篇一个屋子里必须要有多少人，才能让某人和你生日相同的概率至少为1/2? 必须要有多少人，才能让至少两个人生日为 7月 4 日的概率

来源：http://www.yidianzixun.com/article/0oyfiLfl
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！