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

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

每次去掉initial中的一个节点，然后初始化计数num=0，状态数组status={-1}，并且将去掉节点的邻边也去掉，然后深度优先搜索dfs标记所有节点，已经访问过的节点不重复访问并且计数，拿到最小值，若是mi==num则拿到最小索引tp < id

Code

class Solution { public: int n, num; vector<int> status; void dfs(vector<vector<int>>& graph, int start) { status[start] = 1; num++; for(int i = 0; i < graph[start].size(); i++) { if(graph[start][i]==1 && status[i] < 0) { dfs(graph, i); } } } int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) { n = graph.size(); int a, mi = INT_MAX, id, tp; vector<vector<int>> cp = graph; for(int i = 0; i < initial.size(); i++) { num = 0; status.assign(n, -1); graph = cp; tp = initial[i]; for(int k = 0; k < n; k++) { if(graph[tp][k] == 1) { graph[tp][k] = 0; graph[k][tp] = 0; } } graph[tp][tp] = 1; for(int j = 0; j < initial.size(); j++) { if(i==j) continue; a = initial[j]; if(status[a] < 0) { dfs(graph, a); } } if(mi > num) { mi = num; id = tp; } else if(mi==num && tp < id) { mi = num; id = tp; } } return id; } };