1857. Largest Color Value in a Directed Graph Hard

1/**
2 * [1857] Largest Color Value in a Directed Graph
3 *
4 * There is a directed graph of n colored nodes and m edges. The nodes are numbered from 0 to n - 1.
5 * 
6 * 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] = [aj, bj] indicates that there is a directed edge from node aj to node bj.
7 * 
8 * A valid path in the graph is a sequence of nodes x1 -> x2 -> x3 -> ... -> xk such that there is a directed edge from xi to xi+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.
9 * 
10 * Return the largest color value of any valid path in the given graph, or -1 if the graph contains a cycle.
11 * 
12 *  
13 * Example 1:
14 * 
15 * <img alt="" src="https://assets.leetcode.com/uploads/2021/04/21/leet1.png" style="width: 400px; height: 182px;" />
16 * 
17 * 
18 * Input: colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
19 * Output: 3
20 * Explanation: The path 0 -> 2 -> 3 -> 4 contains 3 nodes that are colored "a" (red in the above image).
21 * 
22 * 
23 * Example 2:
24 * 
25 * <img alt="" src="https://assets.leetcode.com/uploads/2021/04/21/leet2.png" style="width: 85px; height: 85px;" />
26 * 
27 * 
28 * Input: colors = "a", edges = [[0,0]]
29 * Output: -1
30 * Explanation: There is a cycle from 0 to 0.
31 * 
32 * 
33 *  
34 * Constraints:
35 * 
36 * 
37 * 	n == colors.length
38 * 	m == edges.length
39 * 	1 <= n <= 10^5
40 * 	0 <= m <= 10^5
41 * 	colors consists of lowercase English letters.
42 * 	0 <= aj, bj < n
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/largest-color-value-in-a-directed-graph/
48// discuss: https://leetcode.com/problems/largest-color-value-in-a-directed-graph/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52impl Solution {
53    pub fn largest_path_value(colors: String, edges: Vec<Vec<i32>>) -> i32 {
54        
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_1857() {
66    }
67}
68