Largest Color Value in a Directed Graph LeetCode solution in C++

1
class Solution {
2
 public:
3
  int largestPathValue(string colors, vector<vector<int>> &edges) {
4
    int n = colors.length();
5
    unordered_map<int, vector<int>> graph;
6
    vector<int> indegree(n, 0);
7

8
    for (auto e : edges) {
9
      graph[e[0]].push_back(e[1]);
10
      indegree[e[1]]++;
11
    }
12

13
    vector<vector<int>> charcount(n, vector<int>(26, 0));
14

15
    queue<int> q;
16

17
    for (int i = 0; i < n; i++) {
18
      if (indegree[i] == 0) {
19
        q.push(i);
20
      }
21
    }
22

23
    int visited = 0, ans = 0;
24

25
    while (!q.empty()) {
26
      int curr = q.front();
27
      q.pop();
28
      visited++;
29

30
      ans = max(ans, ++charcount[curr][colors[curr] - 'a']);
31

32
      for (auto v : graph[curr]) {
33
        indegree[v]--;
34
        if (indegree[v] == 0) q.push(v);
35
        for (int i = 0; i < 26; i++) {
36
          charcount[v][i] = max(charcount[curr][i], charcount[v][i]);
37
        }
38
      }
39
    }
40

41
    if (visited != n) return -1;
42

43
    return ans;
44
  }
45
};