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

2024-03-29 09:52
文章标签 算法 c++ 图论 ii 传播 恶意软件 割点 尽量减少 928

本文主要是介绍【图论】【割点】【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;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/858282。

相关文章

C++中使用vector存储并遍历数据的基本步骤

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库（STL）提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,：本文主要介绍C... 目录（1）容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌（基于哈希表）：‌容器适配器‌：（
阅读更多...
C++中实现调试日志输出

C++中实现调试日志输出

《C++中实现调试日志输出》在C++编程中,调试日志对于定位问题和优化代码至关重要,本文将介绍几种常用的调试日志输出方法,并教你如何在日志中添加时间戳,希望对大家有所帮助... 目录1. 使用 #ifdef _DEBUG 宏2. 加入时间戳：精确到毫秒3.Windows 和 MFC 中的调试日志方法MFC
阅读更多...
Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
深入理解C++ 空类大小

深入理解C++ 空类大小

《深入理解C++空类大小》本文主要介绍了C++空类大小,规定空类大小为1字节,主要是为了保证对象的唯一性和可区分性,满足数组元素地址连续的要求,下面就来了解一下... 目录1. 保证对象的唯一性和可区分性2. 满足数组元素地址连续的要求3. 与C++的对象模型和内存管理机制相适配查看类对象内存在C++中，规
阅读更多...
在 VSCode 中配置 C++ 开发环境的详细教程

在 VSCode 中配置 C++ 开发环境的详细教程

《在VSCode中配置C++开发环境的详细教程》本文详细介绍了如何在VisualStudioCode（VSCode）中配置C++开发环境,包括安装必要的工具、配置编译器、设置调试环境等步骤,通... 目录如何在 VSCode 中配置 C++ 开发环境：详细教程1. 什么是 VSCode？2. 安装 VSCo
阅读更多...
C++11的函数包装器std::function使用示例

C++11的函数包装器std::function使用示例

《C++11的函数包装器std::function使用示例》C++11引入的std::function是最常用的函数包装器,它可以存储任何可调用对象并提供统一的调用接口,以下是关于函数包装器的详细讲解... 目录一、std::function 的基本用法1. 基本语法二、如何使用 std::function
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2