【图论】【割点】【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;
};


扩展阅读

视频课程

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

相关文章
|
6天前
|
算法 C++
c++算法学习笔记 (21) STL
c++算法学习笔记 (21) STL
|
6天前
|
算法 C++
c++算法学习笔记 (20) 哈希表
c++算法学习笔记 (20) 哈希表
|
6天前
|
算法 C++
c++算法学习笔记 (19) 堆
c++算法学习笔记 (19) 堆
|
6天前
|
人工智能 算法 C++
c++算法学习笔记 (18) 约数
c++算法学习笔记 (18) 约数
|
6天前
|
人工智能 算法 C++
c++算法学习笔记 (17) 质数
c++算法学习笔记 (17) 质数
|
6天前
|
算法 C++
c++算法学习笔记 (16) 并查集
c++算法学习笔记 (16) 并查集
|
6天前
|
算法 C++
c++算法学习笔记 (15) 单调栈与单调队列
c++算法学习笔记 (15) 单调栈与单调队列
|
6天前
|
算法 C++
c++算法学习笔记 (14) 栈与队列
c++算法学习笔记 (14) 栈与队列
|
6天前
|
算法 C++
c++算法学习笔记 (13) 链表
c++算法学习笔记 (13) 链表
|
6天前
|
算法 C++
c++算法学习笔记 (12) 区间合并
c++算法学习笔记 (12) 区间合并