【图论】【拓扑排序】1857. 有向图中最大颜色值

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 CTopSort
{
public: 
  void Init(const vector<vector<int>>& vNeiBo)
  {
    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);
      }
    }
    queue<int> que;
    for (int i = 0; i < m_c; i++)
    {
      if (0 == vOutDeg[i])
      {
        que.emplace(i);
        m_vLeaf.emplace_back(i);
        OnDo(-1, i);
      }
    }
    while (que.size())
    {
      const int cur = que.front();
      que.pop();
      for (const auto& next : m_vBackNeiBo[cur])
      {
        vOutDeg[next]--;
        if (0 == vOutDeg[next])
        {
          que.emplace(next);
          OnDo(cur, next);
        }
      }
    };
  }
  int m_c;
  vector<int> m_vLeaf;
protected:
  virtual void OnDo(int pre, int cur) = 0;
  vector<vector<int>> m_vBackNeiBo;
};
class CMyTopSort : public CTopSort
{
public:
  int Do(string& str, vector<vector<int>>& edges)
  {
    m_str = str;
    m_vLen.assign(str.length(), vector<int>(26));
    m_vNeiBo = CNeiBo::Two(str.length(),edges,true);
    CTopSort::Init(m_vNeiBo);
    if (m_iHasDo < m_c)
    {
      return -1;
    }
    int iMax = 0;
    for (const auto& v : m_vLen)
    {
      iMax = max(iMax, *std::max_element(v.begin(), v.end()));
    }
    return iMax;
  }
  vector<vector<int>> m_vLen;
protected:
  // 通过 CTopSort 继承
  virtual void OnDo(int pre, int cur) override
  {
    m_iHasDo++;
    for (int i = 0; i < 26; i++)
    {
      m_vLen[cur][i] = ('a' + i == m_str[cur]);
      int iMax = 0;
      for (const auto& next : m_vNeiBo[cur])
      {
        iMax = max(iMax, m_vLen[next][i]);
      }
      m_vLen[cur][i] += iMax;
    }
  }
  vector<vector<int>> m_vNeiBo;
  string m_str; 
  int m_iHasDo = 0;
};
class Solution {
public:
  int largestPathValue(string colors, vector<vector<int>>& edges) {
    CMyTopSort top;
    return top.Do(colors, edges);
  }
};

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()
{
  string colors;
  vector<vector<int>> edges;
  {
    Solution sln;
    colors = "abaca", edges = { {0,1},{0,2},{2,3},{3,4} };
    auto res = sln.largestPathValue(colors, edges);
    Assert(3, res);
  }
  {
    Solution sln;
    colors = "a", edges = { {0,0} };
    auto res = sln.largestPathValue(colors, edges);
    Assert(-1, res);
  }
}