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
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] = 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
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
#include
#include
using namespace std;
class UnionFind {
public:
vector
vector
// 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
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
int n = graph.size();
vector
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
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
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
cout << minMalwareSpread(graph, initial) << endl;
return 0;
}
c完整代码如下：
#include
#include
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;
}
参考链接
发表评论