【图论】【割点】【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 中每个整数都不同

割点

时间复杂度O(nn),无提升。原理见: 【图论】【并集查找】【C++算法】928. 尽量减少恶意软件的传播 II

代码

class CNeiBo
{
public:	
	static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) 
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
			}
		}
		return vNeiBo;
	}	
	static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<std::pair<int, int>>> vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Grid(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext)
	{
		vector<vector<int>> vNeiBo(rCount * cCount);
		auto Move = [&](int preR, int preC, int r, int c)
		{
			if ((r < 0) || (r >= rCount))
			{
				return;
			}
			if ((c < 0) || (c >= cCount))

			{
				return;
			}
			if (funVilidCur(preR, preC) && funVilidNext(r, c))
			{
				vNeiBo[cCount * preR + preC].emplace_back(r * cCount + c);
			}
		};

		for (int r = 0; r < rCount; r++)
		{
			for (int c = 0; c < cCount; c++)
			{
				Move(r, c, r + 1, c);
				Move(r, c, r - 1, c);
				Move(r, c, r, c + 1);
				Move(r, c, r, c - 1);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
	{
		vector<vector<int>> neiBo(neiBoMat.size());
		for (int i = 0; i < neiBoMat.size(); i++)
		{
			for (int j = i + 1; j < neiBoMat.size(); j++)
			{
				if (neiBoMat[i][j])
				{
					neiBo[i].emplace_back(j);
					neiBo[j].emplace_back(i);
				}
			}
		}
		return neiBo;
	}
};

class CCutPoint
{
public:
	CCutPoint(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size())
	{
		m_vNodeToTime.assign(m_iSize, -1);
		m_vCutNewRegion.resize(m_iSize);		
	}
	void Init(const vector<vector<int>>& vNeiB)
	{
		for (int i = 0; i < m_iSize; i++)
		{
			if (-1 == m_vNodeToTime[i])
			{
				m_vRegionFirstTime.emplace_back(m_iTime);
				dfs(vNeiB, i, -1);
			}
		}
	}	
	const int m_iSize;
	const vector<int>& Time()const { return m_vNodeToTime; }//各节点的时间戳
	const vector<int>& RegionFirstTime()const { return m_vRegionFirstTime; }//各连通区域的最小时间戳
	vector<bool> CalCut()const { 
		vector<bool> ret;
		for (int i = 0; i < m_iSize; i++)
		{
			ret.emplace_back(m_vCutNewRegion[i].size());
		}
		return ret; }//
	const vector < vector<pair<int, int>>>& NewRegion()const { return m_vCutNewRegion; };
protected:
	int dfs(const vector<vector<int>>& vNeiB, const int cur, const int parent)
	{
		int iMinTime = m_vNodeToTime[cur] = m_iTime++;
		OnBeginDFS(cur);
		int iRegionCount = (-1 != parent);//根连通区域数量
		for (const auto& next : vNeiB[cur]) {
			if (next == parent)
			{
				continue;
			}
			if (-1 != m_vNodeToTime[next]) {
				iMinTime = min(iMinTime, m_vNodeToTime[next]);
				continue;
			}
			const int childMinTime = dfs(vNeiB, next, cur);
			iMinTime = min(iMinTime, childMinTime);
			if (childMinTime >= m_vNodeToTime[cur]) {
				iRegionCount++;
				m_vCutNewRegion[cur].emplace_back(m_vNodeToTime[next], m_iTime);
			}
			OnVisitNextEnd(childMinTime,cur, next);
		}
		if (iRegionCount < 2)
		{
			m_vCutNewRegion[cur].clear();
		}
		return iMinTime;
	}
	virtual void OnVisitNextEnd(int childMinTime,int cur, int next) {};
	virtual void OnBeginDFS(int cur) {};
	vector<int> m_vNodeToTime;
	vector<int> m_vRegionFirstTime;
	vector < vector<pair<int, int>>> m_vCutNewRegion; //m_vCutNewRegion[c]如果存在[left,r) 表示割掉c后,时间戳[left,r)的节点会形成新区域
	int m_iTime = 0;
};

class CCutEdge : public CCutPoint
{
public:
	using CCutPoint::CCutPoint;
	vector<vector<int>> m_vCutEdges;
protected:
	virtual void OnVisitNextEnd(int childMinTime, int cur, int next) override {
		if (childMinTime > m_vNodeToTime[cur])
		{
			m_vCutEdges.emplace_back(vector<int>{ cur,next });
		}
	}
};

class CConnectAfterCutPoint 
{
public:
	CConnectAfterCutPoint(const vector<vector<int>>& vNeiB) :m_ct(vNeiB)
	{
		m_ct.Init(vNeiB);
		m_vTimeToNode.resize(m_ct.m_iSize);
		m_vNodeToRegion.resize(m_ct.m_iSize);
		for (int iNode = 0; iNode < m_ct.m_iSize; iNode++)
		{
			m_vTimeToNode[m_ct.Time()[iNode]] = iNode;
		}
		for (int iTime = 0,iRegion= 0; iTime < m_ct.m_iSize; iTime++)
		{
			if ((iRegion < m_ct.RegionFirstTime().size()) && (m_ct.RegionFirstTime()[iRegion] == iTime))
			{
				iRegion++;
			}
			m_vNodeToRegion[m_vTimeToNode[iTime]] = (iRegion - 1);
		}
	}
	bool Connect(int src, int dest, int iCut)const
	{
		if (m_vNodeToRegion[src] != m_vNodeToRegion[dest])
		{
			return false;//不在一个连通区域
		}
		if (0 == m_ct.NewRegion()[iCut].size())
		{//不是割点
			return true;
		}
		const int r1 = GetCutRegion(iCut, src);
		const int r2 = GetCutRegion(iCut, dest);
		return r1 == r2;
	}
	vector<vector<int>> GetSubRegionOfCut(const int iCut)const
	{//删除iCut及和它相连的边后,iCut所在的区域会分成几个区域:父节点一个区域、各子节点		一个区域
			//父节点所在区域可能为空,如果iCut所在的连通区域只有一个节点,则返回一个没有节点的			区域。
		const auto& v = m_ct.NewRegion()[iCut];
		vector<int> vParen;
		const int iRegion = m_vNodeToRegion[iCut];
		const int iEndTime = (iRegion + 1 == m_ct.RegionFirstTime().size()) ? m_ct.m_iSize : m_ct.RegionFirstTime()[iRegion+1];
		vector<vector<int>> vRet;	
		for (int iTime = m_ct.RegionFirstTime()[iRegion],j=-1; iTime < iEndTime; iTime++)
		{
			if (iCut == m_vTimeToNode[iTime])
			{
				continue;
			}
			if ((j + 1 < v.size()) && (v[j + 1].first == iTime))
			{
				j++;
				vRet.emplace_back();
			}
			const int iNode = m_vTimeToNode[iTime];
			if ((-1 != j ) && (iTime >= v[j].first) && (iTime < v[j].second))
			{
				vRet.back().emplace_back(iNode);
			}
			else
			{
				vParen.emplace_back(iNode);
			}			
		}
		vRet.emplace_back();
		vRet.back().swap(vParen);
		return vRet;
	}	
protected:
	int GetCutRegion(int iCut, int iNode)const
	{
		const auto& v = m_ct.NewRegion()[iCut];
		auto it = std::upper_bound(v.begin(), v.end(), m_ct.Time()[iNode], [](int time, const std::pair<int, int>& pr) {return  time < pr.first; });
		if (v.begin() == it)
		{
			return v.size();
		}
		--it;
		return (it->second > m_ct.Time()[iNode]) ? (it - v.begin()) : v.size();
	}
	vector<int> m_vTimeToNode;
	vector<int> m_vNodeToRegion;//各节点所在区域
	CCutPoint m_ct;
};

class CMyCut : public CConnectAfterCutPoint
{
public:
	using CConnectAfterCutPoint::CConnectAfterCutPoint;
	int Do(const unordered_set<int>& setInit)
	{
		vector<int> vM;//各区域感染数量
		vector<int> vInitM;
		for (int iRegion = 0; iRegion < m_ct.RegionFirstTime().size(); iRegion++)
		{
			const auto [iBegin, iEnd] = GetBeginEnd(iRegion);
			const int iInitM = MCount(iBegin, iEnd, setInit);
			vInitM.emplace_back(iInitM);
			vM.emplace_back((iInitM>0) ? (iEnd - iBegin) : 0);
		}
		set<pair<int, int>> setPlusSubIndex;
		for (const auto& iNode : setInit)
		{
			const int iRegion = m_vNodeToRegion[iNode];
			int curSub = vM[iRegion];
			auto subRegion = GetSubRegionOfCut(iNode);
			for (const auto& v : subRegion)
			{
				int iInitM = 0;
				for (const auto& n : v)
				{
					iInitM += setInit.count(n);
				}
				if (iInitM > 0)
				{
					curSub -= v.size();
				}
			}
			setPlusSubIndex.emplace(-curSub, iNode);
		}
		return setPlusSubIndex.begin()->second;
	}
	int MCount(int iBegin,int iEnd, const unordered_set<int>& setInit)
	{
		int iM = 0;
		for (int iTime = iBegin; iTime < iEnd; iTime++)
		{
			const int iNode = m_vTimeToNode[iTime];
			if (setInit.count(iNode))
			{
				iM++;
			}
		}
		return iM;
	}
	pair<int, int> GetBeginEnd(int iRegion)
	{
		const int iEnd = (iRegion + 1 == m_ct.RegionFirstTime().size()) ? m_ct.m_iSize : m_ct.RegionFirstTime()[iRegion + 1];
		return { m_ct.RegionFirstTime()[iRegion] ,iEnd};
	}
};
class Solution {
public:
	int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
		m_c = graph.size();
		unordered_set<int> setInit(initial.begin(), initial.end());
		auto neiBo = CNeiBo::Mat(graph);
		CMyCut cut(neiBo);
		return cut.Do(setInit);
	}
	int m_c;
};

【图论】【割点】【C++算法】928. 尽量减少恶意软件的传播 II,图论,c++,算法,力扣,割点,传播,最少

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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++**实现。

【图论】【割点】【C++算法】928. 尽量减少恶意软件的传播 II,图论,c++,算法,力扣,割点,传播,最少文章来源地址https://www.toymoban.com/news/detail-844692.html

到了这里,关于【图论】【割点】【C++算法】928. 尽量减少恶意软件的传播 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • (全英语版)处理恶意软件的随机森林分类器算法(Random Forest Classifier On Malware)

    Random Forest Classifier On Malware (copyright 2020 by YI SHA, if you want to re-post this,please send me an email:shayi1983end@gmail.com) (全英语版)处理恶意软件的随机森林分类器算法(Random Forest Classifier On Malware) Overview 随机森林分类器是最近很流行的一种识别恶意软件的机器学习算法,由

    2024年02月12日
    浏览(42)
  • C++ [图论算法详解] 欧拉路&欧拉回路

    蒟蒻还在上课,所以文章更新的实在慢了点 那今天就来写一篇这周刚学的欧拉路和欧拉回路吧 在 一个风雪交加的夜晚 18世纪初普鲁士的哥尼斯堡,有一条河穿过,河上有两个小岛,有七座桥把两个岛与河岸联系起来。有个人提出一个问题:一个步行者怎样才能不重复、不遗

    2023年04月14日
    浏览(41)
  • C++ 图论算法之欧拉路径、欧拉回路算法(一笔画完)

    公众号:编程驿站 本文从哥尼斯堡七桥的故事说起。 哥尼斯堡城有一条横贯全市的普雷格尔河,河中的两个岛与两岸用七座桥连结起来。当时那里的居民热衷于一个话题:怎样不重复地走遍七桥,最后回到出发点。这也是经典的一笔画完问题。 1736 年瑞士数学家欧拉( Eul

    2024年04月17日
    浏览(86)
  • 算法——弗洛伊德算法(Floyd-Warshall)(图论)(c++)

    (蒟蒻的第四篇文章,希望dalao勿喷) (希望没问题) 声明: 1.本人变量定义的名称很low 2.本人用的方法也很low 3.但我觉得文章应该不low  (盲目自信) 第四篇文章讲讲Floyd算法 Floyd算法是一种寻找最短路径的常见算法,其特点是: 短,好理解(虽然其他算法也挺好理解的

    2023年04月09日
    浏览(33)
  • C++算法之旅、06 基础篇 | 第三章 图论

    常用代码模板3——搜索与图论 - AcWing 尽可能往深处搜,遇到叶子节点(无路可走)回溯, 恢复现场继续走 数据结构:stack 空间:需要记住路径上的点, (O(h)) 。 ⭐ BFS使用空间少; 无最短路 性质 每个DFS一定对应一个 搜索树 ;要考虑用什么 顺序 遍历所有方案;DFS就是递

    2024年02月10日
    浏览(43)
  • 20 求图的割点和割边—Tarjan算法

    问题描述 去掉2号城市,这样剩下的城市之间就不能两两相互到达。例如4号城市不能到5号城市,6号城市也不能到达1号城市等等。 下面将问题抽象化。在一个无向连通图中,如果删除某个顶点后,图不再连通(即任意两点之间不能相互到达),我们称这样的顶点为割点(或者

    2024年02月15日
    浏览(31)
  • 【C++算法模板】图论-拓扑排序,超详细注释带例题

    推荐视频链接:D01 拓扑排序 给定一张 有向无环图 ,排出所有顶点的一个序列 A A A 满足:对于图中的每条有向边 ( x , y ) (x,y) ( x , y ) , x x x 在 A A A 中都出现在 y y y 之前,则称 A A A 是该图的顶点的一个拓扑序 拓扑排序 可以判断有向图中是否有环,可以生成拓扑序列 对于下

    2024年04月15日
    浏览(39)
  • 浅谈图论——迪杰斯特拉算法(leetcode例题,C++演示)

    如果你想问这个世界上什么算法是最牛逼的?博主是回答不上来的。但是,如果你问博主 什么数据结构是最牛逼 ?博主个人认为 图是最牛逼的数据结构 。因为很多的问题,都可以用图这种数据结构来表示。链表、树这种数据结构博主认为可以看成一种 特殊的图 。所以,博

    2024年02月20日
    浏览(81)
  • 【图论C++】Floyd算法(多源最短路径长 及 完整路径)

    UpData Log👆 2023.9.29 更新进行中 Statement0🥇 一起进步 Statement1💯 有些描述可能不够标准,但能达其意 常见的有: DJ算法 、 Floyd算法 、 A*算法 、 Bellman-Ford 算法 、 SPFA算法 其中 A*算法 是 DJ算法 的plus版, SPFA算法 是 Bellman-Ford 算法 的plus版 算法名称 DJ算法 Floyd算法 SPFA算法

    2024年02月19日
    浏览(42)
  • 《More Effective C++》《基础议题——2、尽量使用C++类型的风格转换》

    类型转换是一般程序员所不能忍受的,但是在紧要关头,类型转换是必须的。C风格的类型转换太过简单,粗暴,不能进行精确的类型转换;为了弥补C转换上功能的不足,C++提供了四种常用的类型转换来应付复杂的转换需求。 static_cast用于在编译时执行类型转换,主要用于相

    2024年01月18日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包