[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