#1857

Largest Color Value in a Directed Graph

expert · 1235 · lc hard +32 · verified · 57.4% accepted · 2,616 likes · top 53%

Description

A directed graph has n nodes colored with lowercase English letters (given by string colors) and directed edges listed in edges[j] = [aj, bj]. The color value of a valid (acyclic) path is the maximum frequency of any single color among the path's nodes.

Return the largest color value over all valid paths, or -1 if the graph has 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.

Code

1

2

3

class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:

class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int: