【图论】【并集查找】【C++算法】928. 尽量减少恶意软件的传播 II

本文主要是介绍【图论】【并集查找】【C++算法】928. 尽量减少恶意软件的传播 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

动态规划的时间复杂度优化

涉及知识点

图论并集查找

LeetCode928. 尽量减少恶意软件的传播 II

给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示。在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
我们可以从 initial 中删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。
请返回移除后能够使 M(initial) 最小化的节点。如果有多个节点满足条件，返回索引最小的节点。
示例 1：
输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输出：0
示例 2：
输入：graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
输出：1
示例 3：
输入：graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
输出：1
提示：
n == graph.length
n == graph[i].length
2 <= n <= 300
graph[i][j] 是 0 或 1.
graph[i][j] == graph[j][i]
graph[i][i] == 1
1 <= initial.length < n
0 <= initial[i] <= n - 1
initial 中每个整数都不同

并集查找

一，将非初始节点连接，行程若干连通区域。
二，计算各连通区域和几个初始节点直接相连。直接相连：连通区域的某点有边和初始节点相连。间接相连：连通区域的某点通过某初始节点连接另外一个初始节点。
$\begin{cases} 一定感染 & 有两个或更多直接相连的初始节点\\ 可以避免 &只有一个直接相连的初始节点。\\ \end{cases}$
间接相连的初始节点不限，因为删除直接相连的节点后，间接相连的节点也断开了。

sum=有和初始节点连接的区域的节点总数量。
maxSub = $Max\Large_{n:initial}$ (只和n相连的区域的节点数量)

注意：
一，一个初始节点可能和一个区域连接多次。
二，删除任何初始节点都不会影响感染数量，返回最小的初始节点，而不是0。

代码

核心代码

class CUnionFind
{
public:CUnionFind(int iSize) :m_vNodeToRegion(iSize){for (int i = 0; i < iSize; i++){m_vNodeToRegion[i] = i;}m_iConnetRegionCount = iSize;}int GetConnectRegionIndex(int iNode){int& iConnectNO = m_vNodeToRegion[iNode];if (iNode == iConnectNO){return iNode;}return iConnectNO = GetConnectRegionIndex(iConnectNO);}void Union(int iNode1, int iNode2){const int iConnectNO1 = GetConnectRegionIndex(iNode1);const int iConnectNO2 = GetConnectRegionIndex(iNode2);if (iConnectNO1 == iConnectNO2){return;}m_iConnetRegionCount--;if (iConnectNO1 > iConnectNO2){UnionConnect(iConnectNO1, iConnectNO2);}else{UnionConnect(iConnectNO2, iConnectNO1);}}bool IsConnect(int iNode1, int iNode2){return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);}int GetConnetRegionCount()const{return m_iConnetRegionCount;}vector<int> GetNodeCountOfRegion()//各联通区域的节点数量{const int iNodeSize = m_vNodeToRegion.size();vector<int> vRet(iNodeSize);for (int i = 0; i < iNodeSize; i++){vRet[GetConnectRegionIndex(i)]++;}return vRet;}std::unordered_map<int, vector<int>> GetNodeOfRegion(){std::unordered_map<int, vector<int>> ret;const int iNodeSize = m_vNodeToRegion.size();for (int i = 0; i < iNodeSize; i++){ret[GetConnectRegionIndex(i)].emplace_back(i);}return ret;}
private:void UnionConnect(int iFrom, int iTo){m_vNodeToRegion[iFrom] = iTo;}vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引int m_iConnetRegionCount;
};class Solution {
public:int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {m_c = graph.size();set<int> setInit(initial.begin(), initial.end());CUnionFind uf(m_c);for (int i = 0; i < m_c; i++){if (setInit.count(i)){continue;}for (int j = i + 1; j < m_c; j++){if (setInit.count(j)){continue;}if (graph[i][j]){uf.Union(i, j);}}}unordered_map<int, int> mRegionInit;for (int i = 0; i < m_c; i++){if (!setInit.count(i)){continue;}for (int j = 0; j < m_c; j++){if (setInit.count(j)){continue;}if (!graph[i][j]){continue;}const int region = uf.GetConnectRegionIndex(j);if (mRegionInit.count(region) && (mRegionInit[region] != i )){//新旧初始节点必须不同mRegionInit[region] = -1;}else{mRegionInit[region] = i;}}}map<int, int> mSub;auto m = uf.GetNodeOfRegion();for (const auto& [region, init] : mRegionInit){	if (-1 != init){mSub[init] += m[region].size();}}int index = -1;int iMax = 0;for (const auto& [tmp, cnt] : mSub){if (cnt > iMax){iMax = cnt;index = tmp;}}return (-1 == index) ? *setInit.begin() : index;}int m_c;
};

测试用例

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{vector<vector<int>> graph;vector<int> initial;{Solution sln;graph = { {1,1,0},{1,1,0},{0,0,1} }, initial = { 0,1 };auto res = sln.minMalwareSpread(graph, initial);Assert(0, res);}{Solution sln;graph = { {1,1,0},{1,1,1},{0,1,1} }, initial = { 0,1 };auto res = sln.minMalwareSpread(graph, initial);Assert(1, res);}{Solution sln;graph = { {1,1,0,0},{1,1,1,0},{0,1,1,1},{0,0,1,1} }, initial = { 0,1 };auto res = sln.minMalwareSpread(graph, initial);Assert(1, res);}{Solution sln;graph = { {1,0,0,0,0,0,0,0,0},{0,1,0,0,0,0,0,0,0},{0,0,1,0,1,0,1,0,0},{0,0,0,1,0,0,0,0,0},{0,0,1,0,1,0,0,0,0},{0,0,0,0,0,1,0,0,0},{0,0,1,0,0,0,1,0,0},{0,0,0,0,0,0,0,1,0},{0,0,0,0,0,0,0,0,1} }, initial = { 6,0,4 };auto res = sln.minMalwareSpread(graph, initial);Assert(0, res);}{Solution sln;graph = { {1,0,0,0,0,0,0,0,1},{0,1,0,1,0,0,0,0,0},{0,0,1,1,0,1,0,0,0},{0,1,1,1,1,0,1,0,0},{0,0,0,1,1,1,0,0,0},{0,0,1,0,1,1,0,0,0},{0,0,0,1,0,0,1,1,0},{0,0,0,0,0,0,1,1,1},{1,0,0,0,0,0,0,1,1} }, initial = { 3,7 };auto res = sln.minMalwareSpread(graph, initial);Assert(3, res);}{Solution sln;graph ={ {1,0,0,0,0,1,0},{0,1,1,0,0,0,0},{0,1,1,0,0,0,0},{0,0,0,1,0,0,0},{0,0,0,0,1,0,0},{1,0,0,0,0,1,0},{0,0,0,0,0,0,1} }, initial = { 4 };auto res = sln.minMalwareSpread(graph, initial);Assert(4, res);}
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛