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)的。
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))
}
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>, 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[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
}
#include
#include
#include
using namespace std;
class unionfind {
public:
vector father;
vector 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 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>& graph, vector& initial) {
int n = graph.size();
vector 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 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[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> graph = { {1, 1, 0}, {1, 1, 0}, {0, 0, 1} };
vector initial = { 0, 1 };
cout << minmalwarespread(graph, initial) << endl;
return 0;
}
#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;
}
