2023-06-10：給定一個(gè)由 n 個(gè)節(jié)點(diǎn)組成的網(wǎng)絡(luò)，用 n x n 個(gè)鄰接矩陣 graph 表示 在節(jié)點(diǎn)
2023-06-10：給定一個(gè)由 n 個(gè)節(jié)點(diǎn)組成的網(wǎng)絡(luò)，用 n x n 個(gè)鄰接矩陣 graph 表示
在節(jié)點(diǎn)網(wǎng)絡(luò)中，只有當(dāng) graph[i][j] = 1 時(shí)，節(jié)點(diǎn) i 能夠直接連接到另一個(gè)節(jié)點(diǎn) j。
一些節(jié)點(diǎn) initial 最初被惡意軟件感染。只要兩個(gè)節(jié)點(diǎn)直接連接，
且其中至少一個(gè)節(jié)點(diǎn)受到惡意軟件的感染，那么兩個(gè)節(jié)點(diǎn)都將被惡意軟件感染。
這種惡意軟件的傳播將繼續(xù)，直到?jīng)]有更多的節(jié)點(diǎn)可以被這種方式感染。
假設(shè) M(initial) 是在惡意軟件停止傳播之后，整個(gè)網(wǎng)絡(luò)中感染惡意軟件的最終節(jié)點(diǎn)數(shù)。
我們可以從 initial 中刪除一個(gè)節(jié)點(diǎn)，
并完全移除該節(jié)點(diǎn)以及從該節(jié)點(diǎn)到任何其他節(jié)點(diǎn)的任何連接。
請返回移除后能夠使 M(initial) 最小化的節(jié)點(diǎn)。
如果有多個(gè)節(jié)點(diǎn)滿足條件，返回索引 最小的節(jié)點(diǎn) 。
initial 中每個(gè)整數(shù)都不同。
輸出：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]。
輸入：0。
答案2023-06-10：
主要思路如下：
1.建立并查集，將感染惡意軟件的節(jié)點(diǎn)標(biāo)記出來。
2.遍歷節(jié)點(diǎn)連接，如果兩個(gè)節(jié)點(diǎn)都沒有被感染，則在并查集中合并這兩個(gè)節(jié)點(diǎn)。
3.對于initial中的每個(gè)節(jié)點(diǎn)，遍歷其能夠直接連接的節(jié)點(diǎn)，如果節(jié)點(diǎn)未被感染，則將其在并查集中的祖先標(biāo)記為initial中的該節(jié)點(diǎn)，如果該祖先已被標(biāo)記為其他initial中的節(jié)點(diǎn)，則將其標(biāo)記為-2。
4.統(tǒng)計(jì)在同一個(gè)initial的所有節(jié)點(diǎn)中，連接的總節(jié)點(diǎn)數(shù)，找出連接數(shù)最多的initial節(jié)點(diǎn)。
5.返回最小索引的節(jié)點(diǎn)。
時(shí)間復(fù)雜度為$O(n^2)$，其中n是節(jié)點(diǎn)數(shù)，因?yàn)橐獙γ總€(gè)節(jié)點(diǎn)進(jìn)行遍歷和合并操作，最壞情況下需要$O(n^2)$次遍歷和合并操作。
空間復(fù)雜度為O(n)，其中n是節(jié)點(diǎn)數(shù)，因?yàn)樾枰褂靡粋€(gè)并查集數(shù)組來存儲節(jié)點(diǎn)的父節(jié)點(diǎn)，另外還需要使用一個(gè)數(shù)組來記錄每個(gè)節(jié)點(diǎn)是否被感染和每個(gè)initial節(jié)點(diǎn)的連接數(shù)量。這些數(shù)據(jù)占用的空間都是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++完整代碼如下：
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完整代碼如下：
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;
}
