<p>There is a <strong>directed graph</strong> of <code>n</code> colored nodes and <code>m</code> edges. The nodes are numbered from <code>0</code> to <code>n - 1</code>.</p>

<p>You are given a string <code>colors</code> where <code>colors[i]</code> is a lowercase English letter representing the <strong>color</strong> of the <code>i<sup>th</sup></code> node in this graph (<strong>0-indexed</strong>). You are also given a 2D array <code>edges</code> where <code>edges[j] = [a<sub>j</sub>, b<sub>j</sub>]</code> indicates that there is a <strong>directed edge</strong> from node <code>a<sub>j</sub></code> to node <code>b<sub>j</sub></code>.</p>

<p>A valid <strong>path</strong> in the graph is a sequence of nodes <code>x<sub>1</sub> -&gt; x<sub>2</sub> -&gt; x<sub>3</sub> -&gt; ... -&gt; x<sub>k</sub></code> such that there is a directed edge from <code>x<sub>i</sub></code> to <code>x<sub>i+1</sub></code> for every <code>1 &lt;= i &lt; k</code>. The <strong>color value</strong> of the path is the number of nodes that are colored the <strong>most frequently</strong> occurring color along that path.</p>

<p>Return <em>the <strong>largest color value</strong> of any valid path in the given graph, or </em><code>-1</code><em> if the graph contains a cycle</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/04/21/leet1.png" style="width: 400px; height: 182px;" /></p>

<pre>
<strong>Input:</strong> colors = &quot;abaca&quot;, edges = [[0,1],[0,2],[2,3],[3,4]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The path 0 -&gt; 2 -&gt; 3 -&gt; 4 contains 3 nodes that are colored <code>&quot;a&quot; (red in the above image)</code>.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/04/21/leet2.png" style="width: 85px; height: 85px;" /></p>

<pre>
<strong>Input:</strong> colors = &quot;a&quot;, edges = [[0,0]]
<strong>Output:</strong> -1
<strong>Explanation:</strong> There is a cycle from 0 to 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == colors.length</code></li>
	<li><code>m == edges.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= m &lt;= 10<sup>5</sup></code></li>
	<li><code>colors</code> consists of lowercase English letters.</li>
	<li><code>0 &lt;= a<sub>j</sub>, b<sub>j</sub>&nbsp;&lt; n</code></li>
</ul>
/*
    https://leetcode.com/problems/largest-color-value-in-a-directed-graph/
    
    Core idea is to first process the nodes that come first in terms of dependency order.
    This ensures that when we process a node, all the paths coming to that node have been processed and
    the node will be processed at the end.
    
    Since we want to explore each path, naive DFS for each path will give TLE.
    We need to save the path color information. To do so, we can use a vector of size 26 for each node.
    This keeps track of longest length path with a given color appearing most frequently.
    
    SOLUTION 1: TOPOLOGICAL SORT (Kahn's Algo)
    In Kahn's algo, each time we are reducing the indegree, we are basically concluding the path traversed
    till that node. So we can do an extra step here, we also give that node the info of max color paths ending there.
    Keep passing on the path color info to each level. Also we use a var to keep track of max value seen so far.
    
    SOLUTION 2: DFS + DP
    This is also topological sort but with DFS. Just like topological sort with DFS, we first explore the neighboring nodes.
    Now here we save the path color info for each node if the traversal starts from there.
    So when a neighbor is done processing, just check the color path lengths that are possible from that neighbor
    and update the info of current node accordingly. Again a var is used to keep track of max value seen.
*/
class Solution {
public:
    /////////////////////////////////////////////////////////////////////// SOLUTION 1: TOPOLOGICAL SORT
    // TC: O(V + E)
    // SC: O(V + E)
    int topologicalSol(vector<unordered_set<int> >& graph, string& colors) {
        int n = graph.size(), processed = 0;
        queue<int> q;
        // indegree[i] = No. of incoming edges to node i
        vector<int> indegree(n, 0);
        // color_path_len[i][c] = For each color c,
        // stores the max no. of times c has been seen in a path ending here at node i  
        vector<vector<int> > color_path_len(n, vector<int>(26, 0));
        // Overall longest same colored nodes in a path
        int max_color = -1;
        
        // Find the indegree for each node
        for(int node = 0; node < n; node++)
            for(auto neighbor: graph[node])
                ++indegree[neighbor];
        
        // Add all the 0 indegree nodes
        for(int node = 0; node < n; node++)
            if(indegree[node] == 0)
                q.emplace(node);
        
        while(!q.empty()) {
            int node = q.front();
            q.pop();
            ++processed;
            
            // Update the max color path info for the current node
            max_color = max(max_color, ++color_path_len[node][colors[node] - 'a']);
                
            // Remove edge from each neighbor
            for(auto neighbor: graph[node]) {
                --indegree[neighbor];
                if(indegree[neighbor] == 0)
                    q.emplace(neighbor);
                
                // Update the color path info for the neighbor
                for(int color = 0; color < 26; color++) {
                    color_path_len[neighbor][color] = max(color_path_len[neighbor][color],
                                                         color_path_len[node][color]);
                }
            }
        }
        
        return processed < n ? -1 : max_color;
    }
    
	/////////////////////////////////////////////////////////////////////////// SOLUTION 2: DFS + DP
    // TC: O(V + E)
    // SC: O(V + E)
    bool dfs(int node, vector<unordered_set<int> >& graph, string& colors, 
             vector<int>& visited, vector<vector<int> >& color_path_len, int& max_color) {
        // Node is currently under processing and we are again seeing it, means a cycle
        if(visited[node] == 1)
            return false;
        
        // Node is unvisited
        if(visited[node] == 0) {
            // Mark node as processing
            visited[node] = 1;
            
            // Explore the neighbors first
            for(auto neighbor: graph[node]) {
                if(!dfs(neighbor, graph, colors, visited, color_path_len, max_color))
                    return false;
                // Since all the paths starting this neighbors have been explored, get the
                // max color path info
                for(int color = 0; color < 26; color++) {
                    color_path_len[node][color] = max(color_path_len[node][color],
                                                     color_path_len[neighbor][color]);
                    max_color = max(max_color, color_path_len[node][color]);
                }
            }
            // Update the color info for current node
            max_color = max(max_color, ++color_path_len[node][colors[node] - 'a']);
            
            // Mark as visited
            visited[node] = 2;
        }
        return true;
    }
    
    int dfsDpSol(vector<unordered_set<int> >& graph, string& colors) {
        int max_color = -1, n = graph.size();
        // visited[i] = {0 (Unvisited), 1 (Processing), 2(Visited)}
        vector<int> visited(n, 0);
        // color_path_len[i][c] = For each color c,
        // stores the max no. of times c has been seen in a path start from here at node i  
        vector<vector<int> > color_path_len(n, vector<int>(26, 0));
        
        for(int node = 0; node < n; node++)
            if(!dfs(node, graph, colors, visited, color_path_len, max_color))
                return -1;
        return max_color;
    }
    
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        // <node, [neighbors] >
        vector<unordered_set<int> > graph(colors.size());
        
        // create the graph
        for(auto edge: edges) 
            graph[edge[0]].emplace(edge[1]);
        
        // return topologicalSol(graph, colors);
        return dfsDpSol(graph, colors);
    }
};
257573