leetcode 困难题 924. Minimize Malware Spread 尽量减少恶意软件的传播

Problem: 924. Minimize Malware Spread 尽量减少恶意软件的传播

先排序initial，然后对initial中的每个数字dfs深度优先搜索，对可以感染的node标记起始数字initial[i]，并且哈希表记录该标记对应的节点数量num，已经标记的节点不重复搜索

最后排除某一个节点，双循环，拿到initial[j]对应的标记a，若标记a没有被访问则累加对应的节点数量ump[a]，不断排除某一个节点，计算剩下节点感染的总和并且拿到最小值

Code

class Solution { public: int n, num; vector<int> status; void dfs(vector<vector<int>>& graph, int start, int mark) { status[start] = mark; num++; for(int i = 0; i < graph[start].size(); i++) { if(graph[start][i]==1 && status[i] < 0) { dfs(graph, i, mark); } } } int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) { n = graph.size(); status.assign(n, -1); int a, id; sort(initial.begin(), initial.end()); unordered_map<int, int> ump; for(int i = 0; i < initial.size(); i++) { a = initial[i]; if(status[a] < 0) { num = 0; dfs(graph, a, a); ump[a] = num; } } int ans, mi = INT_MAX; for(int i = 0; i < initial.size(); i++) { vector<int> tmp(n, -1); ans = 0; for(int j = 0; j < initial.size(); j++) { if(i==j || tmp[status[initial[j]]] > 0) { continue; } a = status[initial[j]]; if(tmp[a] < 0) { tmp[a] = 1; ans += ump[a]; } } if(ans < mi) { mi = ans; id = initial[i]; } } return id; } };