1857: Largest-Color-Value-in-a-Directed-Graph
Hard

Intuitively speaking, you always want to start iterating from a node with indegree 0 (since you are trying to find the path with the highest colour value, it makes sense to start from the beginning of each possible path).

Therefore, a possible solution would be to:

  1. generate the adjacencyArray using edges and calculate each nodes indegree
  2. find all the nodes of indegree 0 and add them to a queue
    • all paths must start from these nodes
  3. run an augmented Breadth-First Search on these nodes
    • first, we update the ans if, out of the 26 colour values, there exists a higher colour value on this node
    • next, when you iterate through all neighbouring nodes:
      • check all 26 colours and update the ones on the neighbouring node that are lower
        • remember to increment the colour of the neighbouring node itself!
      • decrement the indegree counter of the neighbouring node
        • if indegree == 0, then add the node to the queue
          • this is to ensure, we have accounted for all paths that lead into the node, before we continue iterating
          • also, if there is a cycle that includes this node, then the indegree will NEVER equal 0 as there will exist another node pointing to it that we cannot traverse to
    • consequently, that is why we keep track of a seen counter, which we increment for each node from the queue that we pop

Therefore, if seen < (int)colors.size()

Code:

class Solution {
public:
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        // topological sort; then, keep track of colours when iterating through

        // forming the adjacencyArray and calculating each nodes indegree
        vector<vector<int>> colourCount (colors.size(), vector<int>(26));
        vector<int> inDegree (colors.size(), 0);
        vector<vector<int>> adjacencyArray (colors.size());
        for (auto& edge : edges) {
            adjacencyArray[edge[0]].push_back(edge[1]);
            ++inDegree[edge[1]];
        }

        // adding nodes of indegree 0 to the queue
        queue<int> nodes;
        for (int i = 0; i < colors.size(); ++i) {
            if (inDegree[i] == 0) {
                nodes.push(i);
                ++colourCount[i][colors[i]-'a'];
            }
        }

        // slightly-altered Breadth-First Search
        int ans = 0;
        int seenCounter = 0;
        while (!nodes.empty()) {
            int topNode = nodes.front();
            nodes.pop();
            ++seenCounter;
            ans = max(ans, *max_element(colourCount[topNode].begin(), colourCount[topNode].end()));
            for (int& targetNode : adjacencyArray[topNode]) {
                // updating each colour value in each adjacent node 
                for (int i = 0; i < 26; ++i) {
                    colourCount[targetNode][i] = max(colourCount[targetNode][i],
                                                    colourCount[topNode][i] + (i == colors[targetNode] - 'a'));
                }
                // decrement adjacent node indegree & only add to queue if indegree == 0
                --inDegree[targetNode];
                if (inDegree[targetNode] == 0) {
                    nodes.push(targetNode);
                }
            }
        }

        return seenCounter < (int)colors.size() ? -1 : ans;
    }
};

Complexity:

Learnings: