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完整代码如下：
packagemain
import(
"fmt"
"sort"
)
funcminMalwareSpread(graph[][]int,initial[]int)int{
n:=len(graph)
virus:=make([]bool,n)
for_,i:=rangeinitial{
virus[i]=true
}
uf:=NewUnionFind(n)
fori:=0;iforj:=0;jifgraph[i][j]==1&&!virus[i]&&!virus[j]{
uf.Union(i,j)
}
}
}
infect:=make([]int,n)
fori:=rangeinfect{
infect[i]=-1
}
for_,v:=rangeinitial{
fornext:=0;nextifv!=next&&!virus[next]&&graph[v][next]==1{
f:=uf.Find(next)
ifinfect[f]==-1{
infect[f]=v
}elseifinfect[f]!=-2&&infect[f]!=v{
infect[f]=-2
}
}
}
}
cnt:=make([]int,n)
fori:=0;iifinfect[i]>=0{
cnt[infect[i]]+=uf.size[i]
}
}
sort.Ints(initial)
ans:=initial[0]
count:=cnt[ans]
for_,i:=rangeinitial{
ifcnt[i]>count{
ans=i
count=cnt[i]
}
}
returnans
}
typeUnionFindstruct{
father[]int
size[]int
}
funcNewUnionFind(nint)*UnionFind{
father:=make([]int,n)
size:=make([]int,n)
fori:=0;ifather[i]=i
size[i]=1
}
return&UnionFind{father,size}
}
func(uf*UnionFind)Find(iint)int{
help:=make([]int,0)
fori!=uf.father[i]{
help=append(help,i)
i=uf.father[i]
}
for_,v:=rangehelp{
uf.father[v]=i
}
returni
}
func(uf*UnionFind)Union(i,jint){
fi,fj:=uf.Find(i),uf.Find(j)
iffi!=fj{
ifuf.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]
}
}
}
funcmain(){
graph:=[][]int{{1,1,0},{1,1,0},{0,0,1}}
initial:=[]int{0,1}
fmt.Println(minMalwareSpread(graph,initial))
}
rust完整代码如下：
fnmain(){
letgraph=vec![vec![1,1,0],vec![1,1,0],vec![0,0,1]];
letinitial=vec![0,1];
println!("{}",min_malware_spread(graph,initial));
}
structUnionFind{
father:Vec,
size:Vec,
help:Vec,
}
implUnionFind{
fnnew(n:usize)->Self{
letmutfather=vec![0;n];
letmutsize=vec![0;n];
letmuthelp=vec![0;n];
foriin0..n{
father[i]=iasi32;
size[i]=1;
}
Self{father,size,help}
}
fnfind(&mutself,muti:i32)->i32{
letmuthi=0;
whilei!=self.father[iasusize]{
self.help[hiasusize]=i;
hi+=1;
i=self.father[iasusize];
}
whilehi!=0{
hi-=1;
self.father[self.help[hiasusize]asusize]=i;
}
i
}
fnunion(&mutself,i:i32,j:i32){
letfi=self.find(i);
letfj=self.find(j);
iffi!=fj{
ifself.size[fiasusize]>=self.size[fjasusize]{
self.father[fjasusize]=fi;
self.size[fiasusize]+=self.size[fjasusize];
}else{
self.father[fiasusize]=fj;
self.size[fjasusize]+=self.size[fiasusize];
}
}
}
}
fnmin_malware_spread(graph:Vec>,initial:Vec)->i32{
letmutgraph=graph;
letmutinitial=initial;
letn:usize=graph.len();
letmutvirus=vec![false;n];
foriininitial.iter(){
virus[*iasusize]=true;
}
letmutuf=UnionFind::new(n);
foriin0..n{
forjin0..n{
ifgraph[i][j]==1&&!virus[i]&&!virus[j]{
uf.union(iasi32,jasi32);
}
}
}
letmutinfect=vec![-1;n];
for&vininitial.iter(){
fornextin0..n{
ifv!=nextasi32&&!virus[next]&&graph[vasusize][nextasusize]==1{
letf=uf.find(nextasi32);
ifinfect[fasusize]==-1{
infect[fasusize]=v;
}elseifinfect[fasusize]!=-2&&infect[fasusize]!=v{
infect[fasusize]=-2;
}
}
}
}
letmutcnt=vec![0;n];
foriin0..n{
ifinfect[i]>=0{
cnt[infect[i]asusize]+=uf.size[iasusize];
}
}
initial.sort();
letmutans=initial[0];
letmutcount=cnt[ansasusize];
for&iininitial.iter(){
ifcnt[iasusize]>count{
ans=i;
count=cnt[iasusize];
}
}
ans
}
c++完整代码如下：
#include
#include
#include
usingnamespacestd;
classUnionFind{
public:
vectorfather;
vectorsize;
//Constructor
UnionFind(intn){
father.resize(n);
size.resize(n);
for(inti=0;ifather[i]=i;
size[i]=1;
}
}
//Findoperation
intFind(inti){
vectorhelp;
while(i!=father[i]){
help.push_back(i);
i=father[i];
}
for(autov:help){
father[v]=i;
}
returni;
}
//Unionoperation
voidUnion(inti,intj){
intfi=Find(i);
intfj=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];
}
}
}
};
intminMalwareSpread(vector>&graph,vector&initial){
intn=graph.size();
vectorvirus(n,false);
for(autoi:initial){
virus[i]=true;
}
UnionFinduf(n);
for(inti=0;ifor(intj=0;jif(graph[i][j]==1&&!virus[i]&&!virus[j]){
uf.Union(i,j);
}
}
}
vectorinfect(n,-1);
for(autov:initial){
for(intnext=0;nextif(v!=next&&!virus[next]&&graph[v][next]==1){
intf=uf.Find(next);
if(infect[f]==-1){
infect[f]=v;
}
elseif(infect[f]!=-2&&infect[f]!=v){
infect[f]=-2;
}
}
}
}
vectorcnt(n,0);
for(inti=0;iif(infect[i]>=0){
cnt[infect[i]]+=uf.size[i];
}
}
sort(initial.begin(),initial.end());
intans=initial[0];
intcount=cnt[ans];
for(autoi:initial){
if(cnt[i]>count){
ans=i;
count=cnt[i];
}
}
returnans;
}
intmain(){
vector>graph={{1,1,0},{1,1,0},{0,0,1}};
vectorinitial={0,1};
cout<
return0;
}
c完整代码如下：
#include
#include
intcmpfunc(constvoid*a,constvoid*b);
typedefstruct{
int*father;
int*size;
}UnionFind;
UnionFind*createUnionFind(intn){
UnionFind*uf=(UnionFind*)malloc(sizeof(UnionFind));
uf->father=(int*)malloc(n*sizeof(int));
uf->size=(int*)malloc(n*sizeof(int));
for(inti=0;iuf->father[i]=i;
uf->size[i]=1;
}
returnuf;
}
intfind(UnionFind*uf,inti){
inthi=0;
int*help=(int*)malloc(1000*sizeof(int));
while(i!=uf->father[i]){
help[hi]=i;
hi+=1;
i=uf->father[i];
}
for(intj=0;juf->father[help[j]]=i;
}
free(help);
returni;
}
voidunionSet(UnionFind*uf,inti,intj){
intfi=find(uf,i);
intfj=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];
}
}
}
intminMalwareSpread(int**graph,intgraphSize,int*graphColSize,int*initial,intinitialSize){
intn=graphSize;
int*virus=(int*)calloc(n,sizeof(int));
for(inti=0;ivirus[initial[i]]=1;
}
UnionFind*uf=createUnionFind(n);
for(inti=0;ifor(intj=0;jif(graph[i][j]==1&&virus[i]==0&&virus[j]==0){
unionSet(uf,i,j);
}
}
}
int*infect=(int*)malloc(n*sizeof(int));
for(inti=0;iinfect[i]=-1;
}
for(intk=0;kintv=initial[k];
for(intnext=0;nextif(v!=next&&virus[next]==0&&graph[v][next]==1){
intf=find(uf,next);
if(infect[f]==-1){
infect[f]=v;
}
elseif(infect[f]!=-2&&infect[f]!=v){
infect[f]=-2;
}
}
}
}
int*cnt=(int*)calloc(n,sizeof(int));
for(inti=0;iif(infect[i]>=0){
cnt[infect[i]]+=uf->size[i];
}
}
int*sortedInitial=(int*)malloc(initialSize*sizeof(int));
for(inti=0;isortedInitial[i]=initial[i];
}
qsort(sortedInitial,initialSize,sizeof(int),cmpfunc);
intans=sortedInitial[0];
intcount=cnt[ans];
for(inti=0;iif(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);
returnans;
}
intcmpfunc(constvoid*a,constvoid*b){
return(*(int*)a-*(int*)b);
}
intmain(){
intgraphSize=3;
intgraphColSize[]={3,3,3};
intgraphData[][3]={{1,1,0},{1,1,0},{0,0,1}};
int**graph=(int**)malloc(graphSize*sizeof(int*));
for(inti=0;igraph[i]=(int*)malloc(graphColSize[i]*sizeof(int));
for(intj=0;jgraph[i][j]=graphData[i][j];
}
}
intinitial[]={0,1};
intinitialSize=2;
intans=minMalwareSpread(graph,graphSize,graphColSize,initial,initialSize);
printf("%d\n",ans);
for(inti=0;ifree(graph[i]);
}
free(graph);
return0;
}
热门跟贴