题目链接:http://codeforces.com/problemset/problem/919/D
题目大意:给你一个n点m条边的有向图。每个点有一个字符。一条路的权值为这条路上所以字符出现次最大的那个字符的次数。可能有重边,有自环。可能不连通。

求所有路的最大权值。如果可以为无穷大,输出-1。

思路:
先判断如果有环,输出-1。用拓扑排序就可以了。

然后就是一个dp[i][j]表示到第i个节点字符为j的最多个数。
从入度为0的点开始dp。

dp[i][j]=max(dp[i][j], dp[to][j]+(s[i]==j-‘a’)?1:0); 存在边i->to

#include<bits/stdc++.h>
#define LL long long
using namespace std;

char s[300005];
map<int, int> mp[300005];
vector<int> v[300005];
int dp[300005][27];
int indu[300005];
int p=1, N=0;

int Tppx(int n)
{
    queue<int>Q;
    for(int i=1; i<=n; i++)
    {
        if(indu[i]==0)//入度为0
        {
            Q.push(i);
        }
    }
    while(!Q.empty())
    {
        int now=Q.front();
        Q.pop();
        N++;
        for(int i=0; i<v[now].size(); i++)
        {
            int next=v[now][i];
            if(--indu[next]==0)
            {
                Q.push(next);
            }
        }
    }
    if(N!=n)//有环
    {
        return 0;
    }
    return 1;
}


int dfs(int u){

    if(dp[u][0]!=-1){
        return 1;
    }
    if(v[u].size()==0){
        for(int i=0; i<26; i++){
            dp[u][i]=((i==s[u]-'a')?1:0);
        }
        return 1;
    }

    for(int i=0; i<v[u].size(); i++){
        int to=v[u][i];
        dfs(to);
        for(int k=0; k<26; k++){
            dp[u][k]=max(dp[to][k]+((k==s[u]-'a')?1:0), dp[u][k]);
        }
    }
    return 1;
}

int main()
{
    int n, m;
    memset(dp, -1, sizeof(dp));
    scanf("%d%d", &n, &m);
    scanf("%s", s+1);
    for(int i=1; i<=m; i++){
        int u, to;
        scanf("%d%d", &u, &to);
        if(mp[u][to]==0){
            mp[u][to]=1;
            v[u].push_back(to);
            indu[to]++;
        }
    }
    if(Tppx(n)==0){
        printf("-1\n");
        return 0;
    }

    int ans=0;
    for(int i=1; i<=n; i++){
        if(indu[i]==0){
            dfs(i);
            for(int j=0; j<26; j++){
                ans=max(ans, dp[i][j]);
            }
        }
    }
    printf("%d\n", ans);

	return 0;
}