largest-color-value-in-a-directed-graph

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

There is a directed graph of <code>n</code> colored nodes and <code>m</code> edges. The nodes are numbered from <code>0</code> to <code>n - 1</code>.

You are given a string <code>colors</code> where <code>colors[i]</code> is a lowercase English letter representing the color of the <code>ith</code> node in this graph (0-indexed). You are also given a 2D array <code>edges</code> where <code>edges[j] = [aj, bj]</code> indicates that there is a directed edge from node <code>aj</code> to node <code>bj</code>.

A valid path in the graph is a sequence of nodes <code>x1 -&gt; x2 -&gt; x3 -&gt; ... -&gt; xk</code> such that there is a directed edge from <code>xi</code> to <code>xi+1</code> for every <code>1 &lt;= i &lt; k</code>. 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 <code>-1</code> if the graph contains a cycle.

&nbsp;
Example 1:

<img alt="" src="https://assets.leetcode.com/uploads/2021/04/21/leet1.png" style="width: 400px; height: 182px;" />

<pre>
Input: colors = &quot;abaca&quot;, edges = [[0,1],[0,2],[2,3],[3,4]]
Output: 3
Explanation: The path 0 -&gt; 2 -&gt; 3 -&gt; 4 contains 3 nodes that are colored <code>&quot;a&quot; (red in the above image)</code>.
</pre>

Example 2:

<img alt="" src="https://assets.leetcode.com/uploads/2021/04/21/leet2.png" style="width: 85px; height: 85px;" />

<pre>
Input: colors = &quot;a&quot;, edges = [[0,0]]
Output: -1
Explanation: There is a cycle from 0 to 0.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == colors.length</code></li>
	<li><code>m == edges.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>0 &lt;= m &lt;= 105</code></li>
	<li><code>colors</code> consists of lowercase English letters.</li>
	<li><code>0 &lt;= aj, bj&nbsp;&lt; n</code></li>
</ul>

largestPathValue

Largest Color Value in a Directed Graph

Graph

Topological Sort

Memoization

Hash Table

Dynamic Programming

Counting

给你一个 有向图 ，它含有 <code>n</code> 个节点和 <code>m</code> 条边。节点编号从 <code>0</code> 到 <code>n - 1</code> 。

给你一个字符串 <code>colors</code> ，其中 <code>colors[i]</code> 是小写英文字母，表示图中第 <code>i</code> 个节点的 颜色 （下标从 0 开始）。同时给你一个二维数组 <code>edges</code> ，其中 <code>edges[j] = [aj, bj]</code> 表示从节点 <code>aj</code> 到节点 <code>bj</code> 有一条 有向边 。

图中一条有效 路径 是一个点序列 <code>x1 -&gt; x2 -&gt; x3 -&gt; ... -&gt; xk</code> ，对于所有 <code>1 &lt;= i &lt; k</code> ，从 <code>xi</code> 到 <code>xi+1</code> 在图中有一条有向边。路径的 颜色值 是路径中 出现次数最多 颜色的节点数目。

请你返回给定图中有效路径里面的 最大颜色值 。如果图中含有环，请返回 <code>-1</code> 。

 

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2021/04/21/leet1.png" style="width: 400px; height: 182px;">

<pre>输入：colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
输出：3
解释：路径 0 -&gt; 2 -&gt; 3 -&gt; 4 含有 3 个颜色为 <code>"a" 的节点（上图中的红色节点）。</code>
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2021/04/21/leet2.png" style="width: 85px; height: 85px;">

<pre>输入：colors = "a", edges = [[0,0]]
输出：-1
解释：从 0 到 0 有一个环。
</pre>

 

提示：

<ul>
	<li><code>n == colors.length</code></li>
	<li><code>m == edges.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>0 &lt;= m &lt;= 105</code></li>
	<li><code>colors</code> 只含有小写英文字母。</li>
	<li><code>0 &lt;= aj, bj &lt; n</code></li>
</ul>