leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1857.cpp (1212B)

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