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

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

时间：2023-06-10 21:22:39浏览次数：50  
标签：int graph initial 网络 infect uf 节点 size

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(n2)$，其中n是节点数，因为要对每个节点进行遍历和合并操作，最坏情况下需要$O(n2)$次遍历和合并操作。

空间复杂度为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;
}

在这里插入图片描述

标签：int,graph,initial,网络,infect,uf,节点,size
From： https://www.cnblogs.com/moonfdd/p/17471958.html

相关文章

  • 计算机网络中的曼彻斯特编码
    曼彻斯特编码是开放系统互连[OSI]的物理层用于对同步位流的时钟和数据进行编码的一种同步时钟编码技术。RZ的想法和L的想法在曼彻斯特结合数据通信采用不同的编码技术，保证数据安全和传输速度。曼彻斯特编码是数字编码的一个例子。由于每个数据位长度都是默认定义的，因此它与其他数......
  • 【网络（二）】
    下面操作系统不是网络操作系统的是（C）A.NetwareB.Windows2000ServerC.DOSD.LinuxDOS是磁盘操作系统以下哪种协议属于网络层协议（B）A.HTTPSB.ICMPC.SSLD.SNMPTCP/IP是个协议组，可分为三个层次：网络层、传输层和应用层。网络层：IP协议、ICMP协议、ARP协议、RARP协议和BOOTP协议。传......
  • python网络爬虫课程设计--探索Taylor Swift歌词
    python网络爬虫课程设计--探索TaylorSwift歌词一、选题的背景泰勒·斯威夫特（TaylorSwift），1989年12月13日出生于美国宾夕法尼亚州，美国乡村音乐、流行音乐创作女歌手、演员、慈善家。 2006年，与独立唱片公司大机器唱片签约，推出首支单曲《TimMcGraw》与发行首张同名专辑《Taylor......
  • papamelon 348. 修复网络 Wireless Network（挑战程序设计竞赛）
    地址https://www.papamelon.com/problem/348给定N台电脑，它们分别落在地图上的坐标xi,yi上。现在它们都损坏了。我们准备修复其中的某一些电脑。当一台电脑修复好了后，它和其他相距不超过距离d的正常电脑就可以通信。通信具有传递性：A和B能通信，B和C能通信，那么......
  • 网站加速，AdapterMan 是基于 Workerman 的高性能 PHP 异步网络编程框架，可以用于加速任
    AdapterMan是基于Workerman的高性能PHP异步网络编程框架，可以用于加速任意项目。下面是使用AdapterMan进行加速的详细步骤：1.安装AdapterMan：composerrequireadapterman/adapterman 2.创建一个PHP文件，例如`index.php`，并编写以下代码：require_once__DIR__.......
  • adb链接Skyworth(创维)智能网络机顶盒-E900-S
    一、开启USB调试：1.给机顶盒链接网络，有线无线都可以。2.按遥控器上设置，提示输入密码； 常见的密码：（如果下面密码都不对，可以给客服打电话询问）0000 63211008610010100003.选择其他设置 连续按遥控器方向右键5次 出现USB调试 4.ADB链接在机顶盒的“基......
  • 【Sword系列】第七届全国残疾人职业技能大赛样题-网络安全-数据包里有甜甜圈哦~
    前言Wireshark（前称Ethereal）是一个网络数据包分析软件。网络数据包分析软件的功能是截取网络数据包，并尽可能显示出最为详细的网络数据包数据。在过去，网络数据包分析软件是非常昂贵，或是专门属于营利用的软件，Wireshark的出现改变了这一切。在GNU通用公共许可证的保障范围底下，用户可以......
  • python网络爬虫--爬取各省GDP
    一、选题背景1.随着经济全球化的日益深入发展，各国的经济发展也日益重要。在中国，省份是经济发展的基本单位，各省之间经济发展水平的差异较大。了解各省份GDP的数据情况，对于政府部门制定地区经济政策、企业拓展市场等具有重要的参考意义。2.因此，通过Python爬取各省份GPD数据，可......
  • 代码随想录算法训练营第四天|24. 两两交换链表中的节点 ， 19.删除链表的倒数第N个节点
    24.两两交换链表中的节点 个人感觉这个不太难，刚开始打算用步进值为2，来搞，但是没有想到链表应该是怎么样的，原来可以直接用： 1cur=cur->next->next 学到了，这是我自己写的代码：1ListNode*MyLinkedList::swapPairs(ListNode*head)2{3ListNode*dummyHead=new......
  • VSCode使用指定的 SOCKS 代理进行网络连接
    VSCode使用指定的SOCKS代理进行网络连接June10,2023vscode怎么打开settings.json文件？ChatGPT在VisualStudioCode(VSCode)中，打开settings.json文件的步骤如下：打开VisualStudioCode。点击左上角的“文件”菜单，然后选择“首选项”>“设置”(或者你可......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99