【图论】【 割边】【C++算法】1192. 查找集群内的关键连接

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;
  }
};
//割点
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 Solution {
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        auto neiBo = CNeiBo::Two(n, connections, false);
        CCutEdge cut(neiBo);
        cut.Init(neiBo);
        return cut.m_vCutEdges;
    }
};

template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
    int n;
    vector<vector<int>> connections;
  
    {
        Solution sln;
        n = 2, connections = { {0,1} };
        auto res = sln.criticalConnections(n, connections);
        Assert({ { 0,1} }, res);
    }
    {
        Solution sln;
        n = 4, connections = { {0,1},{1,2},{2,0},{1,3} };
        auto res = sln.criticalConnections(n, connections);
        Assert({ { 1,3} }, res);
    }
}