leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1857.cpp (1212B)

      1 class Solution {
      2   public:
      3     int largestPathValue(string colors, vector<vector<int>> &edges) {
      4         int n = colors.size();
      5         vector<unordered_map<int, int>> dp(n);
      6         vector<vector<int>> adj(n);
      7         vector<int> count(n, 0);
      8 
      9         for (auto &edge : edges) {
     10             adj[edge[0]].push_back(edge[1]);
     11             count[edge[1]]++;
     12         }
     13 
     14         queue<int> q;
     15         stack<int> st;
     16 
     17         for (int i = 0; i < n; i++)
     18             if (!count[i]) q.push(i);
     19 
     20         while (!q.empty()) {
     21             int root = q.front();
     22             q.pop();
     23             st.push(root);
     24             for (int child : adj[root]) {
     25                 if (--count[child]) continue;
     26                 q.push(child);
     27             }
     28         }
     29 
     30         for (int i = 0; i < n; i++)
     31             if (count[i]) return -1;
     32 
     33         int res = 0;
     34         while (!st.empty()) {
     35             int root = st.top();
     36             st.pop();
     37             for (int child : adj[root]) {
     38                 for (auto [color, count] : dp[child]) {
     39                     dp[root][color] = max(dp[root][color], count);
     40                 }
     41             }
     42             res = max(res, ++dp[root][colors[root]]);
     43         }
     44         return res;
     45     }
     46 };