Formatted question description: https://leetcode.ca/all/1857.html

# 1857. Largest Color Value in a Directed Graph

## Level

Hard

## Description

There is a **directed graph** of `n`

colored nodes and `m`

edges. The nodes are numbered from `0`

to `n - 1`

.

You are given a string `colors`

where `colors[i]`

is a lowercase English letter representing the **color** of the `i-th`

node in this graph (**0-indexed**). You are also given a 2D array `edges`

where `edges[j] = [a_j, b_j]`

indicates that there is a **directed edge** from node `a_j`

to node `b_j`

.

A valid **path** in the graph is a sequence of nodes `x_1 -> x_2 -> x_3 -> ... -> x_k`

such that there is a directed edge from `x_i`

to `x_(i+1)`

for every `1 <= i < k`

. The **color value** of the path is the number of nodes that are colored the **most frequently** occurring color along that path.

Return *the largest color value of any valid path in the given graph, or -1 if the graph contains a cycle*.

**Example 1:**

**Input:** colors = “abaca”, edges = [[0,1],[0,2],[2,3],[3,4]]

**Output:** 3

**Explanation:** The path 0 -> 2 -> 3 -> 4 contains 3 nodes that are colored “a” (red in the above image).

**Example 2:**

**Input:** colors = “a”, edges = [[0,0]]

**Output:** -1

**Explanation:** There is a cycle from 0 to 0.

**Constraints:**

`n == colors.length`

`m == edges.length`

`1 <= n <= 10^5`

`0 <= m <= 10^5`

`colors`

consists of lowercase English letters.`0 <= a_j, b_j < n`

## Solution

Use topological sort and dynamic programming. Starting from all nodes with indegrees equal to 0, use topological sort to determine whether the graph contains a cycle. If the grapy contains a cycle, return -1. Otherwise, for each node, store the maximum frequency of each color. Maintain the maximum frequency during the process. Finally, return the maximum frequency.

```
class Solution {
public int largestPathValue(String colors, int[][] edges) {
int length = colors.length();
int[] indegrees = new int[length];
Map<Integer, List<Integer>> edgesMap = new HashMap<Integer, List<Integer>>();
for (int[] edge : edges) {
int start = edge[0], end = edge[1];
indegrees[end]++;
List<Integer> list = edgesMap.getOrDefault(start, new ArrayList<Integer>());
list.add(end);
edgesMap.put(start, list);
}
int remain = length;
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < length; i++) {
if (indegrees[i] == 0)
queue.offer(i);
}
int[][] dp = new int[length][26];
while (!queue.isEmpty()) {
int node = queue.poll();
remain--;
dp[node][colors.charAt(node) - 'a']++;
List<Integer> list = edgesMap.getOrDefault(node, new ArrayList<Integer>());
for (int nextNode : list) {
indegrees[nextNode]--;
if (indegrees[nextNode] == 0)
queue.offer(nextNode);
for (int i = 0; i < 26; i++)
dp[nextNode][i] = Math.max(dp[nextNode][i], dp[node][i]);
}
}
if (remain > 0)
return -1;
int maxValue = 0;
for (int i = 0; i < length; i++)
maxValue = Math.max(maxValue, Arrays.stream(dp[i]).max().getAsInt());
return maxValue;
}
}
```