本文涉及的知识点
图论 拓扑排序
LeetCode1857. 有向图中最大颜色值
给你一个 有向图 ，它含有 n 个节点和 m 条边。节点编号从 0 到 n - 1 。
给你一个字符串 colors ，其中 colors[i] 是小写英文字母，表示图中第 i 个节点的 颜色 （下标从 0 开始）。同时给你一个二维数组 edges ，其中 edges[j] = [aj, bj] 表示从节点 aj 到节点 bj 有一条 有向边 。
图中一条有效 路径 是一个点序列 x1 -> x2 -> x3 -> … -> xk ，对于所有 1 <= i < k ，从 xi 到 xi+1 在图中有一条有向边。路径的 颜色值 是路径中 出现次数最多 颜色的节点数目。
请你返回给定图中有效路径里面的 最大颜色值 。如果图中含有环，请返回 -1 。
示例 1：
输入：colors = “abaca”, edges = [[0,1],[0,2],[2,3],[3,4]]
输出：3
解释：路径 0 -> 2 -> 3 -> 4 含有 3 个颜色为 “a” 的节点（上图中的红色节点）。
示例 2：
输入：colors = “a”, edges = [[0,0]]
输出：-1
解释：从 0 到 0 有一个环。
提示：
n == colors.length
m == edges.length
1 <= n <= 105
0 <= m <= 105
colors 只含有小写英文字母。
0 <= aj, bj < n
拓扑排序
建立后邻接表后，直接调用拓扑排序的封装类。
拓扑排序保证排除已经处理节点后，当前节点的出度为0。也就是当前 节点 能够到达的节点都已经处理。这保证无后效性。
每个节点。
如果拓扑排序没有处理完所有节点，说明有环。
m_vLen[cur][i] 表示以cur开始的路径中最多有多少个’a’+i。
时间复杂度： 每个节点最多处理一次，每次处理，处理它所有的临接表。故时间复杂度：O(E)。E是边数。
代码
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); } }
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。
