涉及知识点
图论 割点
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++**实现。
