[LeetCode] Minimize Malware Spread

对于这道题，我们需要明确几点：

1. 如果initial list中的某些节点是其所在component唯一在initial list中的节点的话，如果其所在的component越大，那么将其从initial list remove之后能够减少的感染节点越多。
2. 如果不存在上述的节点，证明每一个component都有至少两个节点在initial list中，那么remove任何一个节点都不会减少被感染的节点数，所以return 0

所以我们只需要dfs寻找满足条件1的所在component最大的节点。如果不存在返回0。时间复杂度O(V + E)，代码如下：

	class Solution {
	public:
	int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
	sort(initial.begin(), initial.end());
	int n = graph.size(), maxCnt = 0, res = -1, len = initial.size();
	vector<int> cnts(n, -1);
	unordered_set<int> visited;
	for (int i = 0; i < len; ++i)
	{
	int start = initial[i], cnt = 0;
	if (visited.find(start) != visited.end())continue;
	dfs(graph, visited, start, cnt);
	cnts[i] = cnt;
	bool onlyMe = true;
	for (int j = 0; j < len; ++j)
	{
	if (j != i && visited.find(initial[j]) != visited.end() && cnts[j] == -1)
	{
	cnts[j] = cnt;
	onlyMe = false;
	}
	}
	if (onlyMe && cnt > maxCnt)
	{
	res = initial[i];
	maxCnt = cnt;
	}
	}
	return res == -1 ? initial[0] : res;
	}
	private:
	void dfs(vector<vector<int>>& graph, unordered_set<int>& visited, int i, int& cnt)
	{
	int n = graph.size();
	if (visited.find(i) != visited.end())return;
	visited.insert(i);
	++cnt;
	for (int j = 0; j < n; ++j)
	{
	if (i != j && graph[i][j])
	dfs(graph, visited, j, cnt);
	}
	}
	};

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