# Problem and explanation

For the problem (It is in Chinese you may need google translate to understand the meaning of this question), 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;    }`

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi