Topological sort and DP

This article is about a problem that can be solved by using both topological sort and DP.

Firstly, we know that the longest path must start from indegree 0 nodes.

Then the dp transition will be

max(f(child)) for child in children

int f[2000];
int dp(int x, vector<vector<int>>& graph){
if (f[x] != -1) return f[x];
int thisret = 0;
for (auto y: graph[x]){
thisret = max(thisret, dp(y, graph) + 1);
}
return f[x] = thisret;
}
int solve(vector<vector<int>>& graph) {
vector<int> zero;
const int n = graph.size();
vector<int> indegree(n, 0);
if (n == 0) return 0;
for (int i =0; i < n; ++i){
for (auto v: graph[i]){
indegree[v] += 1;
}
}
for (int i = 0; i < n; ++i){
if (indegree[i] == 0) zero.push_back(i);
}
memset(f, -1, sizeof f);
int ret = 0;
for (auto x: zero)ret = max(ret, dp(x, graph));
return ret;
}

We can also use the topological sort to update the loss. This is essential bottom-up DP.

int solve(vector<vector<int>>& graph) {
queue<int> zero;

const int n = graph.size();
vector<int> pathLen(n, 0);
vector<int> indegree(n, 0);
if (n == 0) return 0;
for (int i =0; i < n; ++i){
for (auto v: graph[i]){
indegree[v] += 1;
}
}
for (int i = 0; i < n; ++i){
if (indegree[i] == 0) zero.push(i);
}
while (!zero.empty()){
auto u = zero.front(); zero.pop();
for (auto v: graph[u]){
indegree[v] --;
pathLen[v] = max(pathLen[v], pathLen[u] + 1);
if (indegree[v] == 0) zero.push(v);
}
}
int ret = 0;
for (auto len : pathLen) ret = max(ret, len);
return ret;
}

Data Scientist/MLE/SWE @takemobi