# 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;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

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi