time limit: per test3 seconds
memory limit: per test256 megabytes
inputstandard: input
outputstandard: output
You are given a graph with $n$ nodes and $m$ directed edges. One lowercase letter is assigned to each node. We define a path’s value as the number of the most frequently occurring letter. For example, if letters on a path are “abaca”, then the value of that path is $3$. Your task is find a path whose value is the largest.
Input
The first line contains two positive integers $n,m (1≤n,m≤300000)$, denoting that the graph has $n$ nodes and $m$ directed edges.
The second line contains a string $s$ with only lowercase English letters. The $i$-th character is the letter assigned to the $i$-th node.
Then m lines follow. Each line contains two integers $x,y (1≤x,y≤n)$, describing a directed edge from $x$ to $y$. Note that $x$ can be equal to $y$ and there can be multiple edges between $x$ and $y$. Also the graph can be not connected.
Output
Output a single line with a single integer denoting the largest value. If the value can be arbitrarily large, output $-1$ instead.
Examples
input
1 | 5 4 |
output
1 | 3 |
input
1 | 6 6 |
output
1 | -1 |
input
1 | 10 14 |
output
1 | 4 |
Note
In the first sample, the path with largest value is $1→3→4→5$. The value is $3$ because the letter ‘a’ appears $3$ times.
题意
给出有$n$个点和$m$条边的有向图,每个节点上有一个小写字母,求所有通路中出现次数最多的字母出现的次数,如果出现了无数次,输出$-1$
Solve
用拓扑排序判断图中是否有环,如果有环,那么环上的字母出现的次数为无限多次,输出$-1$。
如果能够进行拓扑排序,对于每次遍历的节点,更新当前路上字母出现次数的最大值
$dp[i][j]$表示到达节点$i$,字母$’a’+j$出现的最大次数
Code
1 |
|