題意：在節(jié)點(diǎn)網(wǎng)絡(luò)中景用，只有當(dāng) graph[i][j] = 1?時(shí)涵叮，每個(gè)節(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ù)京髓。
我們可以從初始列表中刪除一個(gè)節(jié)點(diǎn)航缀。如果移除這一節(jié)點(diǎn)將最小化 M(initial)，?則返回該節(jié)點(diǎn)堰怨。如果有多個(gè)節(jié)點(diǎn)滿足條件芥玉，就返回索引最小的節(jié)點(diǎn)。
請(qǐng)注意备图，如果某個(gè)節(jié)點(diǎn)已從受感染節(jié)點(diǎn)的列表 initial 中刪除灿巧，它以后可能仍然因惡意軟件傳播而受到感染。
示例 1：
輸入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
輸出：0
示例 2：
輸入：graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
輸出：0
示例 3：
輸入：graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
輸出：1
思路：枚舉initial里每個(gè)節(jié)點(diǎn)揽涮，求如果這個(gè)節(jié)點(diǎn)沒有被感染抠藕，最終有多少個(gè)節(jié)點(diǎn)會(huì)被感染。
每次重新構(gòu)造并查集蒋困，最后枚舉每個(gè)節(jié)點(diǎn)盾似，如果這個(gè)節(jié)點(diǎn)在initial里面或者這個(gè)節(jié)點(diǎn)所屬的集合，即father[i]被感染了雪标，那么該節(jié)點(diǎn)被感染了零院。
復(fù)雜度：O(N ^ 3 * log N)
C++代碼：
class?Solution?{
public:
????int?father[100010];
????int?getfa(int?u){
????????if(father[u]?==?u)?return?u;
????????father[u]?=?getfa(father[u]);
????????return?father[u];
????}
????void?merge(int?u,?int?v){
????????int?fu?=?getfa(u);
????????int?fv?=?getfa(v);
????????if(fu?!=?fv)?father[fv]?=?fu;
????}
????int?flag[500];
????int?minMalwareSpread(vector<vector<int>>&?graph,?vector<int>&?initial)?{
????????int?N?=?graph.size();
????????if(N?==?0)?return?0;
????????int?res?=?-1;
????????int?resnode?=?0;
????????for(int?k?=?0;?k?<?initial.size();?k++){
????????????memset(flag,?0,?sizeof(flag));
????????????for(int?i?=?0;?i?<?initial.size();?i++){
????????????????if(i?!=?k)?flag[initial[i]]?=?true;
????????????}
????????????for(int?i?=0;?i?<?N;?i++){
????????????????father[i]?=?i;
????????????}
????????????for(int?i?=?0;?i?<?N;?i++){
????????????????for(int?j?=?0;?j?<?N;?j++){
????????????????????int?fa?=?getfa(i);
????????????????????if(i?!=?j?&&?(flag[i]?||?flag[fa])?&&?graph[i][j]){
????????????????????????merge(i,?j);
????????????????????}
????????????????}
????????????}
????????????int?sum?=?0;
????????????for(int?i?=?0;?i?<?N;?i++){
????????????????int?fa?=?getfa(i);
????????????????if(flag[fa])?sum?++;
????????????}
????????????if(res?==?-1)?{
????????????????res?=?sum;
????????????????resnode?=?initial[k];
????????????}
????????????else?if(res?>?sum){
????????????????res?=?sum;
????????????????resnode?=?initial[k];
????????????}
????????????else?if(res?==?sum?&&?initial[k]?<?resnode){
????????????????resnode?=?initial[k];
????????????}
????????????cout?<<?initial[k]?<<?"?"?<<?res?<<?"?"?<<?sum?<<?endl;
????????}
????????return?resnode;
????}
};
/*
[[1,0,1],[0,1,1],[1,1,1]]
[2,1]
*/
