class Solution {
public int largestPathValue(String colors, int[][] edges) {
int n = colors.length(), ans = 0;
List<List<Integer>> graph = new ArrayList<>(n);
for (int i = 0; i < n; ++i) graph.add(new ArrayList<>());
int[] degree = new int[n];
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
++degree[edge[1]];
}
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; ++i) if (degree[i] == 0) queue.offer(i);
int[][] dp = new int[n][26];
while (!queue.isEmpty()) {
int u = queue.poll();
++dp[u][colors.charAt(u) - 'a'];
--n;
if (graph.get(u).isEmpty()) {
for (int c = 0; c < 26; ++c) ans = Math.max(ans, dp[u][c]);
continue;
}
for (int v : graph.get(u)) {
for (int c = 0; c < 26; ++c) dp[v][c] = Math.max(dp[v][c], dp[u][c]);
if (--degree[v] == 0) queue.offer(v);
}
}
return n == 0 ? ans : -1;
}
}
class Solution:
def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
n = len(colors)
# 邻接表
g = collections.defaultdict(list)
# 节点的入度统计，用于找出拓扑排序中最开始的节点
indeg = [0] * n
for x, y in edges:
indeg[y] += 1
g[x].append(y)
# 记录拓扑排序过程中遇到的节点个数
# 如果最终 found 的值不为 n，说明图中存在环
found = 0
f = [[0] * 26 for _ in range(n)]
q = collections.deque()
for i in range(n):
if indeg[i] == 0:
q.append(i)
while q:
found += 1
u = q.popleft()
# 将节点 u 对应的颜色增加 1
f[u][ord(colors[u]) - ord("a")] += 1
# 枚举 u 的后继节点 v
for v in g[u]:
indeg[v] -= 1
# 将 f(v,c) 更新为其与 f(u,c) 的较大值
for c in range(26):
f[v][c] = max(f[v][c], f[u][c])
if indeg[v] == 0:
q.append(v)
if found != n:
return -1
ans = 0
for i in range(n):
ans = max(ans, max(f[i]))
return ans
class Solution {
public:
int largestPathValue(string colors, vector<vector<int>>& edges) {
int n = colors.size();
// 邻接表
vector<vector<int>> g(n);
// 节点的入度统计，用于找出拓扑排序中最开始的节点
vector<int> indeg(n);
for (auto&& edge: edges) {
++indeg[edge[1]];
g[edge[0]].push_back(edge[1]);
}
// 记录拓扑排序过程中遇到的节点个数
// 如果最终 found 的值不为 n，说明图中存在环
int found = 0;
vector<array<int, 26>> f(n);
queue<int> q;
for (int i = 0; i < n; ++i) {
if (!indeg[i]) {
q.push(i);
}
}
while (!q.empty()) {
++found;
int u = q.front();
q.pop();
// 将节点 u 对应的颜色增加 1
++f[u][colors[u] - 'a'];
// 枚举 u 的后继节点 v
for (int v: g[u]) {
--indeg[v];
// 将 f(v,c) 更新为其与 f(u,c) 的较大值
for (int c = 0; c < 26; ++c) {
f[v][c] = max(f[v][c], f[u][c]);
}
if (!indeg[v]) {
q.push(v);
}
}
}
if (found != n) {
return -1;
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, *max_element(f[i].begin(), f[i].end()));
}
return ans;
}
};
// 按照拓扑序 DP
func largestPathValue(colors string, edges [][]int) (ans int) {
n := len(colors)
g := make([][]int, n)
deg := make([]int, n)
for _, e := range edges {
v, w := e[0], e[1]
if v == w {
return -1
}
g[v] = append(g[v], w)
deg[w]++
}
cnt := 0
dp := make([][26]int, n)
q := []int{}
for i, d := range deg {
if d == 0 {
q = append(q, i)
}
}
for len(q) > 0 {
v := q[0]
q = q[1:]
cnt++
dp[v][colors[v]-'a']++
ans = max(ans, dp[v][colors[v]-'a'])
for _, w := range g[v] {
for i, c := range dp[v] {
dp[w][i] = max(dp[w][i], c)
}
if deg[w]--; deg[w] == 0 {
q = append(q, w)
}
}
}
if cnt < n {
return -1
}
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
