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.
The first line contains two positive integers n, m (1 ≤ n, m ≤ 300 000), 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 a single line with a single integer denoting the largest value. If the value can be arbitrarily large, output -1 instead.
5 4
abaca
1 2
1 3
3 4
4 5
3
6 6
xzyabc
1 2
3 1
2 3
5 4
4 3
6 4
-1
10 14
xzyzyzyzqx
1 2
2 4
3 5
4 5
2 6
6 8
6 5
2 10
3 9
10 9
4 6
1 10
2 8
3 7
4
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.
题意：给一个由字母代替节点的有向图，一条路径的值为出现次数最多的字母出现次数，求出路径的最大值（如果无穷大输出-1）
思路：有环就是-1，接下来就是DAG，暴力26个字母，对于当前字母x，将所有为x的节点权值设为1，其它节点权值设为0，就是一个非常简单的DP了。
代码：
1 //#include "bits/stdc++.h" 2 #include "cstdio" 3 #include "map" 4 #include "set" 5 #include "cmath" 6 #include "queue" 7 #include "vector" 8 #include "string" 9 #include "cstring" 10 #include "time.h" 11 #include "iostream" 12 #include "stdlib.h" 13 #include "algorithm" 14 #define db double 15 #define ll long long 16 #define vec vector<ll> 17 #define Mt vector<vec> 18 #define ci(x) scanf("%d",&x) 19 #define cd(x) scanf("%lf",&x) 20 #define cl(x) scanf("%lld",&x) 21 #define pi(x) printf("%d ",x) 22 #define pd(x) printf("%f ",x) 23 #define pl(x) printf("%lld ",x) 24 #define inf 0x3f3f3f3f 25 #define rep(i, x, y) for(int i=x;i<=y;i++) 26 const int N = 3e5 + 5; 27 const int mod = 1e9 + 7; 28 const int MOD = mod - 1; 29 const db eps = 1e-10; 30 const db PI = acos(-1.0); 31 using namespace std; 32 vector<int> g[N]; 33 queue<int> q; 34 char s[N]; 35 int in[N],deg[N],vis[N],f[N],val[N]; 36 int n,m,ans; 37 bool cal()//判环 38 { 39 int cnt=0; 40 for(int i=1;i<=n;i++){ 41 if(!in[i]) q.push(i),cnt++; 42 vis[i]=1; 43 } 44 while(q.size()){ 45 int v=q.front(); 46 q.pop(); 47 for(int i=0;i<g[v].size();i++){ 48 int vv=g[v][i]; 49 in[vv]--; 50 if(!in[vv]) vis[vv]=1,q.push(vv),cnt++; 51 } 52 } 53 return cnt==n; 54 } 55 void dfs(int u)//DP（DAG） 56 { 57 f[u]=val[u]; 58 vis[u]=1; 59 for(int i=0;i<g[u].size();i++){ 60 int v=g[u][i]; 61 if(!vis[v]) dfs(v); 62 f[u]=max(f[u],f[v]+val[u]); 63 } 64 ans=max(f[u],ans); 65 } 66 int main() 67 { 68 ci(n),ci(m); 69 scanf("%s",s+1); 70 for(int i=0;i<m;i++){ 71 int x,y; 72 ci(x),ci(y); 73 g[x].push_back(y); 74 in[y]++,deg[y]++; 75 } 76 if(!cal()) puts("-1"); 77 else 78 { 79 for(int i=0;i<26;i++){ 80 memset(vis,0, sizeof(vis)); 81 memset(f,0, sizeof(f)); 82 for(int j=1;j<=n;j++){//节点赋值 83 if(s[j]=='a'+i) val[j]=1; 84 else val[j]=0; 85 } 86 for(int j=1;j<=n;j++){ 87 if(!deg[j]) dfs(j); 88 } 89 } 90 pi(ans); 91 } 92 return 0; 93 }