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

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

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 中每个整数都不同

## 代码

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

## 扩展阅读

#### 视频课程

https://edu.csdn.net/course/detail/38771

https://edu.csdn.net/lecturer/6176

#### 相关下载

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

#### 测试环境

|
6天前
|

c++算法学习笔记 (21) STL
c++算法学习笔记 (21) STL
13 0
|
6天前
|

c++算法学习笔记 (20) 哈希表
c++算法学习笔记 (20) 哈希表
12 0
|
6天前
|

c++算法学习笔记 (19) 堆
c++算法学习笔记 (19) 堆
13 0
|
6天前
|

c++算法学习笔记 (18) 约数
c++算法学习笔记 (18) 约数
12 1
|
6天前
|

c++算法学习笔记 (17) 质数
c++算法学习笔记 (17) 质数
16 5
|
6天前
|

c++算法学习笔记 (16) 并查集
c++算法学习笔记 (16) 并查集
14 1
|
6天前
|

c++算法学习笔记 (15) 单调栈与单调队列
c++算法学习笔记 (15) 单调栈与单调队列
14 2
|
6天前
|

c++算法学习笔记 (14) 栈与队列
c++算法学习笔记 (14) 栈与队列
14 0
|
6天前
|

c++算法学习笔记 (13) 链表
c++算法学习笔记 (13) 链表
15 2
|
6天前
|

c++算法学习笔记 (12) 区间合并
c++算法学习笔记 (12) 区间合并
15 2