Topological sort and DP


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) {
int tsi = 0;
while (zeros.size()){
auto j = zeros.front();zeros.pop();
ts[tsi++] = j;
for (auto nei : graph[j]){
if (indegree[nei] == 0) zeros.push(nei);
if (tsi != n) {
cout << -1;
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<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;




Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store