【图论】【基环内向树】【广度优先】【深度优先】2127. 参加会议的最多员工数

class CTopSort
{
public: 
  template <class T = vector<int> >
  void Init(const vector<T>& vNeiBo,bool bDirect = true )
  {
    const int iDelOutDeg = bDirect ? 0 : 1;
    m_c = vNeiBo.size();
    m_vBackNeiBo.resize(m_c);
    vector<int> vOutDeg(m_c);
    for (int cur = 0; cur < m_c; cur++)
    {
      vOutDeg[cur] = vNeiBo[cur].size();  
      for (const auto& next : vNeiBo[cur])
      {
        m_vBackNeiBo[next].emplace_back(cur);
      }
    }
    vector<bool> m_vHasDo(m_c);
    queue<int> que;
    for (int i = 0; i < m_c; i++)
    {
      if ( vOutDeg[i] <= iDelOutDeg)
      {
        m_vHasDo[i] = true;
        if (OnDo(i)) {
          que.emplace(i);
        }
      }
    }
    while (que.size())
    {
      const int cur = que.front();
      que.pop();
      for (const auto& next : m_vBackNeiBo[cur])
      {
        if (m_vHasDo[next] )
        {
          continue;
        }       
        vOutDeg[next]--;
        if (vOutDeg[next] <= iDelOutDeg )
        {
          m_vHasDo[next] = true;
          if (OnDo(next)) {
            que.emplace(next);
          }
        }
      }
    };
  }
  int m_c;
protected:
  virtual bool OnDo( int cur) = 0;
  vector<vector<int>> m_vBackNeiBo; 
  
};
class CMyTopSort : public CTopSort
{
public:
  CMyTopSort(int iSize)
  {
    m_bCyc.assign(iSize,true);
  }
  vector<bool> m_bCyc;
protected:
  virtual bool OnDo(int cur) override
  {
    m_bCyc[cur] = false;
    return true;
  }
};
class Solution {
public:
  int maximumInvitations(vector<int>& favorite) {
    m_c = favorite.size();
    CMyTopSort topSort(m_c);
    vector<vector<int>> vNeiBo(m_c);
    for (int i = 0; i < m_c; i++)
    {
      vNeiBo[favorite[i]].emplace_back(i);
    }
    topSort.Init(vNeiBo);
    vector<bool> vVisit(m_c);
    int iMaxLenCyc = 0;
    int iCyc2 = 0;
    for (int i = 0; i < m_c; i++)
    {
      if ((!topSort.m_bCyc[i]) || vVisit[i])
      {
        continue;
      }
      int len = 0;      
      int next = i;
      do
      {
        vVisit[next] = true;
        next = favorite[next];        
        len++;
      } while (i != next);
      iMaxLenCyc = max(iMaxLenCyc, len);
      if (2 == len)
      {
        iCyc2 += DFS(i,vNeiBo, topSort) + DFS(favorite[i], vNeiBo, topSort);
      }
    }
    return max(iCyc2, iMaxLenCyc);
  }
  int DFS(int cur, vector<vector<int>>& vNeiBo, CMyTopSort& topSort)
  {
    int iMaxChildLen = 0;
    for (const auto& next : vNeiBo[cur])
    {
      if (topSort.m_bCyc[next])
      {
        continue;
      }
      iMaxChildLen = max(iMaxChildLen, DFS(next,vNeiBo,topSort));
    }
    return iMaxChildLen + 1;
  }
  int m_c;
};

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()
{
  vector<int> favorite;
  {
    Solution sln;
    favorite = { 2, 2, 1, 2 };
    auto res = sln.maximumInvitations(favorite);
    Assert(3, res);
  }
  {
    Solution sln;
    favorite = { 1,2,0 };
    auto res = sln.maximumInvitations(favorite);
    Assert(3, res);
  }
  {
    Solution sln;
    favorite = { 3,0,1,4,1 };
    auto res = sln.maximumInvitations(favorite);
    Assert(4, res);
  }
}