Topological sort and DP

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

Longest Path in a Graph

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

Topological sort

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