1.题目描述

链接：924. 尽量减少恶意软件的传播 – 力扣（LeetCode）

给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。

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

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

如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。

请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。

示例

输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]

输出：0

输入：graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]

输出：0

2.题目分析

思路1

一道hard题，需要注意几个细节：1.移除这个节点只是把“感染属性”给移除了，也就是它不能够主动感染，但是还是可能被间接感染的。2.感染可能会出现多次间接感染，查找需要查找完。

思路：1.对于每一个initial当中感染的节点，查找它构成的连通图，这里采用BFS的方式，如果其他initial的节点也在这个连通图当中，那么这几个在同一个连通图的initial节点删除也没有用，因为还会被感染，所以不用考虑；2.因为连通数量可能是多次间接的，因此用一个count去记录每一个initial感染节点所能感染的节点数；3.都会被感染的时候返回最小的index

思路2

采用官方题解的思路，1.一开始找到所有的连通分量，并记录每个节点所在的连通分量；2.记录每个连通分量的大小；3.遍历initial，记录每一个感染节点对应的连通分量，如果多个节点对应同一个连通分量，则删除也没有用，因此我们需要找到对应感染节点数只为1的连通分量

3.代码实现

思路1代码实现

class Solution {
private:
	unordered_set<int>initSet;
	bool findArrive(vector<vector<int>>& graph, vector<int>& initial, vector<bool>& arrive,int index, vector<int>&count)
	{
		bool add = false;  //判断节点是否会被相互感染
		stack<int>q;
		q.push(initial[index]);
		while (!q.empty())
		{
			int i = q.top();
			q.pop();
			for (int j = 0; j < graph.size(); ++j)
			{
				if (graph[i][j] && !arrive[j])
				{
					q.push(j);
					arrive[j] = true;
					count[index]++;
					if(initSet.count(j) && j != initial[index])
						add = true;
				}
					
			}
		}
		return add;
	}
public:
	int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
		const int N = initial.size();
		int minIndex = graph.size();
		//sort(initial.begin(), initial.end());
		initSet = std::move(unordered_set<int>(initial.begin(), initial.end()));
		vector<bool>arrive(graph.size(), false);
		vector<int>count(N);
		for (int i = 0; i < N; ++i)
		{
			//对于任意一个节点查找它所能感染的其他所有节点，然后看是不是在initial里面
			//这里对于没有感染也会报错
			if (!arrive[initial[i]])
			{
				arrive[initial[i]] = true;
				if(!findArrive(graph, initial, arrive,i,count))
					arrive[initial[i]] = false;
			}
			minIndex = min(minIndex, initial[i]);
		}

		//记录不会被相互感染的initial节点
		vector<int>single;
		for (int i = 0; i < N; ++i)
		{
			if (!arrive[initial[i]])
				single.push_back(i);
		}		
		if (single.empty())
			return minIndex;

		minIndex = initial[single[0]];
		int maxValue = 0;
		for (int i = 0; i < single.size(); ++i)
		{
			if (count[single[i]] > maxValue)
			{
				minIndex = initial[single[i]];
				maxValue = count[single[i]];
			}
			else if (count[single[i]] == maxValue)
				minIndex = min(minIndex, initial[single[i]]);
		}
		return minIndex;
	}
};

思路2代码实现

class Solution {
public:
	int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
		//官方思路重写
		const int N = graph.size();
		queue<int>q;
		vector<int>idIn(N);
		unordered_map<int, int>id_to_size;  //记录连通分量大小
		int id = 0;
		for (int i = 0; i < N; ++i)
		{
			if (!idIn[i])  //这个节点没有连通分量
			{
				++id;
				idIn[i] = id;
				int size = 1;
				q.push(i);
				while (!q.empty())
				{
					int index = q.front();
					q.pop();
					for (int j = 0; j < N; ++j)
					{
						if (!idIn[j] && graph[index][j])
						{
							idIn[j] = id;
							++size;
							q.push(j);
						}
					}
				}
				id_to_size[id] = size;
			}
		}

		unordered_map<int, int>node_to_id;
		for (int node : initial)
		{
			node_to_id[idIn[node]]++;
		}
		int minIndex = N + 1;
		int maxValue = 0;
		for (int node : initial)
		{
			int remove = node_to_id[idIn[node]] == 1 ? id_to_size[idIn[node]] : 0;
			if (maxValue < remove || (maxValue == remove && node < minIndex))
			{
				maxValue = remove;
				minIndex = node;
			}
		}
		return minIndex;
	}
};