• 【图论】【并集查找】【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 中每个整数都不同

    并集查找

    一，将非初始节点连接，行程若干连通区域。
    二，计算各连通区域和几个初始节点直接相连。 直接相连：连通区域的某点有边和初始节点相连。间接相连：连通区域的某点通过某初始节点连接另外一个初始节点。
    { 一定感染 有两个或更多直接相连的初始节点 可以避免 只有一个直接相连的初始节点。 {一定感染有两个或更多直接相连的初始节点可以避免只有一个直接相连的初始节点。

    {一定感染可以避免​有两个或更多直接相连的初始节点只有一个直接相连的初始节点。​
    间接相连的初始节点不限，因为删除直接相连的节点后，间接相连的节点也断开了。

    sum=有和初始节点连接的区域的节点总数量。
    maxSub = M a x n : i n i t i a l Max\Large_{n:initial} Maxn: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;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152

    测试用例

    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);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62

    扩展阅读

    视频课程

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

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

    相关下载

    想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
    https://download.csdn.net/download/he_zhidan/88348653

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

    测试环境

    操作系统：win7 开发环境： VS2019 C++17
    或者 操作系统：win10 开发环境： VS2022 C++17
    如无特殊说明，本算法用**C++**实现。

  • 相关阅读:
    9.4 链表删除指定节点（静态创建链表）
    短视频矩阵系统，抖音矩阵系统，抖音SEO源码。
    基于生物地理学算法优化的BP神经网络（预测应用） - 附代码
    【自然语言处理】【实体匹配】PromptEM：用于低资源广义实体匹配的Prompt-tuning
    Python打包成exe文件
    MongoDB复制（副本集）总结
    【数据结构】线段树
    你应该知道的数仓安全：都是同名Schema惹的祸
    6 - 字典
    NSE脚本使用
  • 原文地址：https://blog.csdn.net/he_zhidan/article/details/136155420