【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目(三)

简介: 【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目

【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目(二)https://developer.aliyun.com/article/1478724


2024年3月9号 新封装

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;
  }
};
class CUnionFind
{
public:
  CUnionFind(int iSize) :m_vNodeToRegion(iSize)
  {
    for (int i = 0; i < iSize; i++)
    {
      m_vNodeToRegion[i] = i;
    }
    m_iConnetRegionCount = iSize;
  } 
  CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size())
  {
    for (int i = 0; i < vNeiBo.size(); i++) {
      for (const auto& n : vNeiBo[i]) {
        Union(i, n);
      }
    }
  }
  int GetConnectRegionIndex(int iNode)
  {
    int& iConnectNO = m_vNodeToRegion[iNode];
    if (iNode == iConnectNO)
    {
      return iNode;
    }
    return iConnectNO = GetConnectRegionIndex(iConnectNO);
  }
  void Union(int iNode1, int iNode2)
  {
    const int iConnectNO1 = GetConnectRegionIndex(iNode1);
    const int iConnectNO2 = GetConnectRegionIndex(iNode2);
    if (iConnectNO1 == iConnectNO2)
    {
      return;
    }
    m_iConnetRegionCount--;
    if (iConnectNO1 > iConnectNO2)
    {
      UnionConnect(iConnectNO1, iConnectNO2);
    }
    else
    {
      UnionConnect(iConnectNO2, iConnectNO1);
    }
  }
  bool IsConnect(int iNode1, int iNode2)
  {
    return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
  }
  int GetConnetRegionCount()const
  {
    return m_iConnetRegionCount;
  }
  vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
  {
    const int iNodeSize = m_vNodeToRegion.size();
    vector<int> vRet(iNodeSize);
    for (int i = 0; i < iNodeSize; i++)
    {
      vRet[GetConnectRegionIndex(i)]++;
    }
    return vRet;
  }
  std::unordered_map<int, vector<int>> GetNodeOfRegion()
  {
    std::unordered_map<int, vector<int>> ret;
    const int iNodeSize = m_vNodeToRegion.size();
    for (int i = 0; i < iNodeSize; i++)
    {
      ret[GetConnectRegionIndex(i)].emplace_back(i);
    }
    return ret;
  }
private:
  void UnionConnect(int iFrom, int iTo)
  {
    m_vNodeToRegion[iFrom] = iTo;
  }
  vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引,为了增加可理解性,用最小索引
  int m_iConnetRegionCount;
};
class CParents
{
public:
  CParents(vector<int>& vParent, const int iMaxLeve)
  { 
    int iBitNum = 0;
    for (; (1 << iBitNum) < iMaxLeve; iBitNum++);
    const int n = vParent.size();
    m_vParents.assign(iBitNum+1, vector<int>(n, -1));
    m_vParents[0] = vParent;
    //树上倍增
    for (int i = 1; i < m_vParents.size(); i++)
    {
      for (int j = 0; j < n; j++)
      {
        const int iPre = m_vParents[i - 1][j];
        if (-1 != iPre)
        {
          m_vParents[i][j] = m_vParents[i - 1][iPre];
        }
      }
    }
  }
  int GetParent(int iNode, int iLeve)const
  {
    int iParent = iNode;
    for (int iBit = 0; iBit < m_vParents.size(); iBit++)
    {
      if (-1 == iParent)
      {
        return iParent;
      }
      if (iLeve & (1 << iBit))
      {
        iParent = m_vParents[iBit][iParent];
      }
    }
    return iParent;
  } 
protected:
  vector<vector<int>> m_vParents;
};
class C2Parents : CParents
{
public:
  C2Parents(vector<int>& vParent, const vector<int>& vLeve) :m_vLeve(vLeve)
    , CParents(vParent,*std::max_element(vLeve.begin(), vLeve.end()))
  {   
  } 
  int GetPublicParent(int iNode1, int iNode2)const
  {
    int leve0 = m_vLeve[iNode1];
    int leve1 = m_vLeve[iNode2];
    if (leve0 < leve1)
    {
      iNode2 = GetParent(iNode2, leve1 - leve0);
      leve1 = leve0;
    }
    else
    {
      iNode1 = GetParent(iNode1, leve0 - leve1);
      leve0 = leve1;
    }
    //二分查找
    int left = -1, r = leve0;
    while (r - left > 1)
    {
      const auto mid = left + (r - left) / 2;
      const int iParent0 = GetParent(iNode1, mid);
      const int iParent1 = GetParent(iNode2, mid);
      if (iParent0 == iParent1)
      {
        r = mid;
      }
      else
      {
        left = mid;
      }
    }
    return GetParent(iNode1, r);
  }
protected:
  vector<vector<int>> m_vParents;
  const vector<int> m_vLeve;
};
//割点
class CCutPoint
{
public:
  CCutPoint(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size())
  {
    m_vNodeToTime.assign(m_iSize, -1);
    m_vCutNewRegion.resize(m_iSize);
    for (int i = 0; i < m_iSize; i++)
    {
      if (-1 == m_vNodeToTime[i])
      {
        m_vRegionFirstTime.emplace_back(m_iTime);
        dfs(vNeiB, i, -1);
      }
    } 
  }
  int dfs(const vector<vector<int>>& vNeiB,const int cur, const int parent)
  {
    int iMinTime = m_vNodeToTime[cur] = m_iTime++;
    int iRegionCount = (-1 != parent);//根连通区域数量
    for (const auto& next : vNeiB[cur])   {
      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);
      }
    }
    if (iRegionCount < 2)
    {
      m_vCutNewRegion[cur].clear();
    }
    return iMinTime;
  }
  const int m_iSize;
  const vector<int>& Time()const { return m_vNodeToTime; }//各节点的时间戳
  const vector<int>& RegionFirstTime()const { return m_vRegionFirstTime; }//各连通区域的最小时间戳
  vector<bool> Cut()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:
  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 CConnectAfterCutPoint 
{
public:
  CConnectAfterCutPoint(const vector<vector<int>>& vNeiB) :m_ct(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;//各节点所在区域
  const CCutPoint m_ct;
};
class Solution {
public:
  vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
    m_c = edges.size() + 1;
    m_vDisToRoot.resize(m_c);
    m_vParent.resize(m_c);
    m_vLeve.resize(m_c);
    auto neiBo = CNeiBo::Three(m_c, edges, false, 0);
    DFS(neiBo, 0, -1, 0, 0);
    C2Parents par(m_vParent, m_vLeve);
    auto neiBo2 = CNeiBo::Two(m_c, edges, false, 0);
    CConnectAfterCutPoint cut(neiBo2);
    vector<int> vRet(m_c);
    for (int c = 0; c < m_c; c++)
    {
      auto regs = cut.GetSubRegionOfCut(c);
      int left = 0;
      int& iRet = vRet[c];
      for (const auto& subRegion : regs)
      {
        int cur = 0;
        for (const auto& ab : subRegion)
        {
          const int pub = par.GetPublicParent(ab, c);
          const int len = m_vDisToRoot[ab] + m_vDisToRoot[c] - 2 * m_vDisToRoot[pub];
          if (0 != len % signalSpeed)
          {
            continue;
          }
          cur++;
        }
        iRet += left * cur;
        left += cur;
      }
    }
    return vRet;
  }
  void DFS(vector<vector<std::pair<int, int>>>& neiBo, int cur, int par, int leve, int dis)
  {
    m_vDisToRoot[cur] = dis;
    m_vParent[cur] = par;
    m_vLeve[cur] = leve;
    for (const auto& [next, len] : neiBo[cur])
    {
      if (next == par)
      {
        continue;
      }
      DFS(neiBo, next, cur, leve + 1, dis + len);
    }
  }
  vector<int> m_vDisToRoot, m_vParent, m_vLeve;
  int m_c;
};

DFS代替树上倍增

时间复杂度的瓶颈在 树上倍增。可以直接DFS 最近公共祖先。


扩展阅读

视频课程

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

相关文章
|
3月前
|
JSON 监控 API
在线网络PING接口检测服务器连通状态免费API教程
接口盒子提供免费PING检测API,可测试域名或IP的连通性与响应速度,支持指定地域节点,适用于服务器运维和网络监控。
|
3月前
|
机器学习/深度学习 存储 监控
内部文件审计:企业文件服务器审计对网络安全提升有哪些帮助?
企业文件服务器审计是保障信息安全、确保合规的关键措施。DataSecurity Plus 是由卓豪ManageEngine推出的审计工具,提供全面的文件访问监控、实时异常告警、用户行为分析及合规报告生成功能,助力企业防范数据泄露风险,满足GDPR、等保等多项合规要求,为企业的稳健发展保驾护航。
|
4月前
|
存储 运维 API
HPE OneView 10.0 - HPE 服务器、存储和网络设备集中管理软件
HPE OneView 10.0 - HPE 服务器、存储和网络设备集中管理软件
84 1
|
2月前
|
存储 弹性计算 网络协议
阿里云服务器ECS实例规格族是什么?不同规格CPU型号、处理器主频及网络性能参数均不同
阿里云ECS实例规格族是指具有不同性能特点和适用场景的实例类型集合。不同规格族如计算型c9i、通用算力型u1、经济型e等,在CPU型号、主频、网络性能、云盘IOPS等方面存在差异。即使CPU和内存配置相同,性能参数和价格也各不相同,适用于不同业务需求。
|
2月前
|
存储 监控 Linux
Dell OpenManage Enterprise 4.5 - Dell 服务器、存储和网络设备集中管理软件
Dell OpenManage Enterprise 4.5 - Dell 服务器、存储和网络设备集中管理软件
46 0
|
2月前
|
Windows
电脑显示有问题,电脑连接不上网络,电脑没声音,电脑链接不上打印机?驱动人生就能解决所有问题
电脑显示有问题,电脑连接不上网络,电脑没声音,电脑链接不上打印机?驱动人生就能解决所有问题
71 0
|
3月前
|
安全
基于Reactor模式的高性能服务器之Acceptor组件(处理连接)
本节介绍了对底层 Socket 进行封装的设计与实现,通过 `Socket` 类隐藏系统调用细节,提供简洁、安全、可读性强的接口。重点包括 `Socket` 类的核心作用(管理 `sockfd_`)、成员函数的功能(如绑定地址、监听、接受连接等),以及 `Acceptor` 组件的职责:监听连接、接收新客户端连接并分发给上层处理。同时说明了 `Acceptor` 与 `EventLoop` 和 `TcpServer` 的协作关系,并展示了其成员变量和关键函数的工作机制。
73 2
|
2月前
|
SQL Oracle 关系型数据库
【赵渝强老师】Oracle客户端与服务器端连接建立的过程
Oracle数据库采用客户端-服务器架构,客户端通过其网络环境与服务器通信,实现数据库访问。监听程序负责建立连接,通过命令lsnrctl可启动、停止及查看监听状态。本文介绍了监听器的作用及相关基础管理操作。
103 0
|
5月前
|
存储 安全 Linux
Dell OpenManage Enterprise 4.4 - Dell 服务器、存储和网络设备集中管理软件
Dell OpenManage Enterprise 4.4 - Dell 服务器、存储和网络设备集中管理软件
127 4
Dell OpenManage Enterprise 4.4 - Dell 服务器、存储和网络设备集中管理软件

热门文章

最新文章