[LeetCode]Minimize Malware Spread II

这道题Brute Force的做法就可以，我们依次把每个节点从initial list和图中移除，然后bfs看最后能够感染多少节点，取最少的就是答案。时间复杂度O((V + E) * N)，V为节点数，E为边数，N为initial list的长度。代码如下:

	class Solution {
	public:
	int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
	sort(initial.begin(), initial.end());
	int n = graph.size(), minCnt = INT_MAX, res = -1, len = initial.size();
	unordered_set<int> visited;
	for (int i = 0; i < len; ++i)
	{
	int cnt = bfs(graph, initial, initial[i]);
	if(cnt < minCnt)
	{
	minCnt = cnt;
	res = initial[i];
	}
	}
	return res;
	}
	private:
	int bfs(vector<vector<int>>& graph, vector<int>& initial, int hole)
	{
	queue<int> q;
	for(auto& node : initial)
	if(node != hole)
	q.push(node);
	int cnt = 0;
	unordered_set<int> visited;
	visited.insert(hole);
	while(q.size())
	{
	auto node = q.front();
	q.pop();
	if(visited.find(node) != visited.end())continue;
	++cnt;
	visited.insert(node);
	for (int j = 0; j < graph.size(); ++j)
	{
	if (node != j && graph[node][j])
	q.push(j);
	}
	}
	return cnt;
	}
	};

view raw Minimize Malware Spread II.cpp hosted with ❤ by GitHub