描述

在节点网络中，只有当 graph[i][j] = 1 时，每个节点 i 能够直接连接到另一个节点 j 。

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

我们可以从初始列表中删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。如果移除这一节点将最小化 M(initial)， 则返回该节点。如果有多个节点满足条件，就返回索引最小的节点。

1. 1 < graph.length = graph[0].length <= 300
2. 0 <= graph[i][j] == graph[j][i] <= 1
3. graph[i][i] = 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;     } }; 

更多题解参考