Topological sort and DP

Introduction

We know that DP can be solved by building toplogical sort graph. If you are not very clear about this, please check this article.

Problem and explanation

For the problem (It is in Chinese you may need google translate to understand the meaning of this question)here, we can solve it by first finding the topological sorting results and then from there, run a DP to solve the problem.

Reference Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
void  solve(int n, vector<vector<int>>& graph, vector<int> & indegree, string& code){
    vector<int> cnt(26, 0);
    for (auto c: code) cnt[c - 'a'] ++;
    // topological sort
    vector<int> ts(n);
    queue<int> zeros;
    for (int i = 0; i < n; ++i){
        if (indegree[i] == 0) {
            zeros.push(i);
        }
    }
    int tsi = 0;
    while (zeros.size()){
        auto j = zeros.front();zeros.pop();
        ts[tsi++] = j;
        for (auto nei : graph[j]){
            indegree[nei]--;
            if (indegree[nei] == 0) zeros.push(nei);
        }
    }
    if (tsi != n) {
        cout << -1;
        return;
    }
    int ret = 0;
    int dp[n];
    // check the longest path from a to z by visiting the node reversely of the topological sort.
    // recall that dp can be solved by using topological sort.
    for (char ch = 'a'; ch <= 'z'; ++ch){
        if (cnt[ch - 'a'] <= ret) continue;
        memset(dp, 0, sizeof dp);
        for (int i = n-1; i >=0; --i){
            int node = ts[i];
            int v = code[node] == ch;
            dp[node] = v;
            for (auto nei: graph[node]){
                dp[node] = max(dp[node], v + dp[nei]);
            }
            ret = max(ret, dp[node]);
        }
    }
    cout << ret << endl;
}
int main()
{
    int n, m;
    cin >> n >> m;
    string code;
    cin >> code;
    vector<vector<int>>graph(n);
    vector<int> indegree(n, 0);
    bool selfCycle = false;
    for (int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        if (u==v) selfCycle= true;
        graph[u - 1].push_back(v - 1);
        indegree[v - 1]++;
    }
    if (selfCycle) cout << -1 << endl;
    else {
       solve(n, graph, indegree, code);
    }
    return 0;
    
}