Codefroces 919D Substring（拓扑排序+DP）

题目链接：http://codeforces.com/problemset/problem/919/D

题目大意：给你一张有向图，给你每个顶点上的字母和一些边，让你找出一条路径，路径上的相同字母数最多，输出最大相同字母数，若可以无穷多则输出-1（成环）。

解题思路：因为是有向图，所以可以直接利用拓扑排序，拓扑排序过程中用f[i][j]记录到第i个点为止的路径，出现字母j的最大出现次数即可。

代码：

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<vector>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=3e5+;

 int n,m;

 int f[N][],deg[N];

 char ch[N];

 vector<int>v[N];

 int toposort(){

     queue<int>q;

     int ans=-;

     for(int i=;i<=n;i++){

         if(deg[i]==)

             q.push(i);

     }

     int cnt=;

     while(!q.empty()){

         int k=q.front();

         q.pop();

         cnt++;

         f[k][ch[k]-'a']++;

         ans=max(f[k][ch[k]-'a'],ans);

         for(int i=;i<v[k].size();i++){

             int t=v[k][i];

             deg[t]--;

             for(int j=;j<;j++){

                 f[t][j]=max(f[t][j],f[k][j]);

             }

             if(deg[t]==){

                 q.push(t);

             }

         }

     }

     if(cnt!=n)

         ans=-;

     return ans;

 }

 int main(){

     scanf("%d%d",&n,&m);

     getchar();

     for(int i=;i<=n;i++){

         scanf("%c",&ch[i]);

     }

     for(int i=;i<=m;i++){

         int a,b;

         scanf("%d%d",&a,&b);

         deg[b]++;

         v[a].push_back(b);

     }

     printf("%d\n",toposort());

     return ;

 }