CodeForces - 919D Substring (拓扑排序+dp)

题意：将一个字符串上的n个字符视作点，给出m条有向边，求图中路径上最长出现的相同字母数。

分析：首先如果这张图中有环，则可以取无限大的字符数，在求拓扑排序的同时可以确定是否存在环。

之后在拓扑排序的结果上分别对26个字母dp求出最大结果，并取最大值（一定要分别对每个字母dp，否则会出现问题）。

#include<bits/stdc++.h>

using namespace std;

const int maxn =3e5+;

int N,M;

vector<int> G[maxn];

vector<int> topo;

int indeg[maxn];

int dp[maxn][];

char str[maxn];

void init()

{

    topo.clear();

    memset(indeg,,sizeof(indeg));

    for(int i=;i<=N;++i)   G[i].clear();

}

bool circle()

{

    int v,u,cnt=;

    queue<int> Q;

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

        if(!indeg[i]){

            Q.push(i);

            cnt++;

        }

    }

    while(!Q.empty()){

        v= Q.front(); Q.pop();

        topo.push_back(v);

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

            u =G[v][i];

            indeg[u]--;

            if(!indeg[u]){

                Q.push(u);

                cnt++;

            }

        }

    }

    if(cnt==N) return false;

    else return true;

}

int solve(int key)

{

    memset(dp,,sizeof(dp));

    int res=;

    int e,v,u;

    for(int i =;i<topo.size();++i){

        v =topo[i];

        e = str[v]-'a';

        if(e==key)

            dp[v][e]++;

        res = max(res,dp[v][key]);

        for(int j = ;j<G[v].size();++j){

            u = G[v][j];

            dp[u][key]= max(dp[u][key],dp[v][key]);

        }

    }

    return res;

}

int main()

{

    int v,u;

    while(~scanf("%d%d",&N,&M)){

        init();

        scanf("%s",str+);

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

            scanf("%d%d",&v,&u);

            G[v].push_back(u);

            indeg[u]++;

        }

        if(circle()){

            printf("-1\n");

            continue;

        }

        int res=;

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

            res=max(res,solve(i));

        }

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

    }

    return ;

}