题意：
思路：
51nod的强化版
由于题目中存在环，对于环上的字母来说，每个字母都会出现无穷次，所以答案为i n f，输出− 1
如果不存在环，该图就是一个D A G，枚举每个字母，拓扑排序后用d p求解这个字母出现的最多次数就好。
判环的话：如果t o p s o r t 后仍有字母的入度> 0，说明有环。
代码：
const int maxn=3e5+100; vector<int>g[maxn]; int n,m,dp[maxn][28],din[maxn]; char s[maxn]; int topsort(){ queue<int>q; int siz=0; rep(i,1,n) if(din[i]==0){ q.push(i); dp[i][s[i]-'a']=1; siz++; } while(!q.empty()){ int t=q.front();q.pop(); for(auto v:g[t]){ rep(i,0,25){ int tt=0; if(i==s[v]-'a') tt++; dp[v][i]=max(dp[v][i],dp[t][i]+tt); } if(--din[v]==0) q.push(v),siz++; } } rep(i,1,n) if(din[i]>0) return -1; int ans=0; rep(i,1,n) if(g[i].size()==0){ rep(j,0,25) ans=max(ans,dp[i][j]); } return ans; } int main(){ n=read,m=read; scanf("%s",s+1); rep(i,1,m){ int u=read,v=read; din[v]++; g[u].push_back(v); } cout<<topsort(); return 0; }
