[leetcode/lintcode 題解] 算法面試真題詳解：盡量減少惡意軟體的傳播II

描述

在節點網絡中，隻有當graphi = 1 時，每個節點i能夠直接連接配接到另一個節點j。

一些節點initial最初被惡意軟體感染。隻要兩個節點直接連接配接，且其中至少一個節點受到惡意軟體的感染，那麼兩個節點都将被惡意軟體感染。這種惡意軟體的傳播将繼續，直到沒有更多的節點可以被這種方式感染。

假設 M(initial) 是在惡意軟體停止傳播之後，整個網絡中感染惡意軟體的最終節點數。

我們可以從初始清單中删除一個節點，并完全移除該節點以及從該節點到任何其他節點的任何連接配接。如果移除這一節點将最小化 M(initial)， 則傳回該節點。如果有多個節點滿足條件，就傳回索引最小的節點。

1. 1 < graph.length = graph[0].length <= 300
2. 0 <= graphi == graphj <= 1
3. graphi = 1
4. 1 <= initial.length < graph.length
5. 0 <= initial[i] < graph.length

線上評測位址：

領扣題庫官網

樣例1
輸入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
輸出：0
解釋：移除0然後隻有1被感染。           

樣例2
輸入：graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
輸出：1
解釋：移除1然後隻有0被感染。           

考點

• 圖論
• 搜尋

題解

從受感染的頂點（起始頂點編号）開始dfs染色，直到找不到另一個受感染的頂點。如果目前頂點已具有其他顔色，将其排除（設定為-2）。答案是出現最多次的顔色對應的受感染的頂點或“受感染”的最小頂點（如果所有頂點至少染色2次）。

class Solution {
public:
    vector<int> col;    
        
    void dfs(vector<vector<int>>& g,unordered_set<int> &hs,int v,int c) {
        col[v] = col[v] == -1 ? c:-2;
        for(int i = 0;i < g.size();++i){
            if(g[v][i] && !hs.count(i) && col[i] != c && col[i] != -2) {
                dfs(g,hs,i,c);
            }
        }
    }
        
    int minMalwareSpread(vector<vector<int>>& g, vector<int>& in) {
        unordered_map<int,int> hm;        
        unordered_set<int> hs(in.begin(),in.end());
        int n = g.size(), res, mx=0;
        col.resize(n,-1);
        for(auto v:in) dfs(g,hs,v,v);
        for(auto v:col) {
            if(v >= 0) {
                if(++hm[v] > mx) {
                    res = v;
                    mx = hm[v];
                }
                else if(hm[v] == mx) {
                    res = min(res,v);
                }
            }
        }
        if(hm.empty()) { 
            return *min_element(in.begin(),in.end());
        }
        return res;
    }
};
           

更多題解參考：

九章官網solution