Find cycle in directed graph and topological sort and DP

LC 1857. Largest Color Value in a Directed Graph

LC 1857. Largest Color Value in a Directed Graph

Using topological sort can check whether a directed graph has cycle or not.

Using topolocial sort again to update the max color by:

traverse the 26 possible color j,

current_node’s max color = max(current_node color, prev_node_color + current_node_color == color j)

class Solution {
public:
string colors;
     vector<vector<int>>graph;
// standard way to find cycle in a directed graph by using topolocial sort. 
// the topolocial sort is finished based on BFS.
     bool has_cycle(vector<int> indegree, int n){
        vector<int> topo_res;
        queue<int> Q;
        for (int i = 0; i < n; ++i){
            if (indegree[i] == 0){
                topo_res.push_back(i);
                Q.push(i);
            }
        }
        while (!Q.empty()){
            int node = Q.front();Q.pop();
            for (auto nei: graph[node]){
                indegree[nei]--;
                if (indegree[nei] == 0){
                    Q.push(nei);
                    topo_res.push_back(nei);
                }
            }
        }
        return topo_res.size() != n;
}
 void find_max_color(vector<int> indegree,  vector<vector<int>>&largest_color, int &ret)
 {
    queue<int> Q;
    const int n = colors.size();
    for (int i = 0; i < n; ++i)
    {
        if (indegree[i] == 0)
            {
                Q.push(i);
                largest_color[i][colors[i] - 'a'] += 1;
            }
    }
    ret = 1;
    while (!Q.empty())
        {
            int node = Q.front();Q.pop();
          
            for (auto nei: graph[node])
            {
                indegree[nei]--;
                int idx = colors[nei] - 'a';
                for (int j = 0; j < 26; ++j)
                {
                    largest_color[nei][j] = max(largest_color[nei][j], largest_color[node][j] + (idx== j));
                    ret = max(ret,  largest_color[nei][j]);
                }
                if (indegree[nei] == 0)
                {
                    Q.push(nei);
                }
            }
        }
}
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        const int n = colors.size();
        vector<vector<int>>graph(n);
        vector<int> indegree(n, 0);
        for (auto e: edges){
            graph[e[0]].push_back(e[1]);
            indegree[e[1]]++;
        }
        this->colors = colors;
        this->graph = graph;
        if (has_cycle( indegree,  n))return -1;
       
        vector<vector<int>>largest_color(n, vector<int>(26, 0));
        int ret = 0;
        find_max_color(indegree, largest_color, ret);
        return ret;
        
    }
};

Since DP has a close relationship to topological sort, we can also think this solution is based on the DP method.

Thanks for reading.