Topological sort, cycle finding in directed graph and DFS with memo

LeetCode 1857 Largest Color Value in a Directed Graph

Problem

1857. Largest Color Value in a Directed Graph

Explanation

This problem is the 4th question of the weekly contest on May 8, 2021. In order to solve this problem, we should be familiar with:

• Topological sort
• How to check whether we have cycles in a graph: directed graph and undirected graph.
• DFS

Topological sort is a classical one, and I will not give explanation. Pls check this post to recall this classical algorithm. Actually, that post already tells us how to check whether it has cycle in a directed graph.

How to find cycle in a undirected graph is not needed to solve this problem, however, if the readers are interested in this, pls check this post and this one.

After finshing the cycle finding step, we can cut this problem into:

find the longest path has color “a”

find the longest path has color “b”

…

In total, we have 26 cases. For each one, we can solve it by using DFS to traverse the whole graph. We can begin from the zero indegree nodes.

We need memorize the results to avoid over-computing for the following case:

If we don’t memo the results, the green nodes’ will be computed 4 times.

Complexity

time complexity of this algorithm is:

Topological sort: O(V) where V is number of nodes.

DFS: O(26*V) where V is number of nodes.

Code

int memo[100010];
const int INF = 1e9;
class Solution {
public:
    string colors;
    vector<vector<int>> AL;
    int dfs(int node, int j){
        if (memo[node]!=-1) return memo[node];
        int val = (colors[node] - 'a') == j;
        if (AL[node].empty()) return memo[node] = val;
         int ret = -INF;
        for (auto v: AL[node]) ret = max(ret, val + dfs(v, j));
        return memo[node] = ret;
    }
    
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        this->colors = colors;
        int ret = -INF;
        const int n = colors.size();
        vector<int> indegree(n, 0);
        vector<vector<int>> AL(n);
        for (auto &x: edges) {
            indegree[x[1]]++;
            AL[x[0]].push_back(x[1]);
        }
        this->AL = AL;
        queue<int> Q, zero;
        for (int f=0; f<n;++f){
            if (indegree[f] ==0) {
                Q.push(f); zero.push(f); 
            } 
        }
        // Check whether the directed graph has cycle.
        int num=0;
        while (!Q.empty()) {
            auto node = Q.front(); Q.pop();
            num++;
            for (auto &v : AL[node]){
                indegree[v]--;
                if(indegree[v] == 0) Q.push(v);
            }
        }
        if (num != n) return -1;
        while (!zero.empty()) {
            auto x = zero.front();zero.pop();
            for (int j = 0; j < 26; ++j){
                memset(memo, -1, sizeof memo);
                ret = max(ret, dfs(x, j));
            }
        }
        return ret; 
    }
};

Thanks for reading. For the whole article list of my posts in different categories, please visit my blog.