Topological sort and DP

Introduction

Problem and explanation

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