leetcode

commit af5b8eae8f485b6d2e43ee4dbc3438a5800fdcbb
parent 546dc79fdfe45a4a83af84ef08f25fb857fc0f99
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun,  9 Apr 2023 21:13:41 +0200

Daily Problem

Diffstat:
A
Problems/1857.cpp
 | 
46
++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 47 insertions(+), 0 deletions(-)
diff --git a/Problems/1857.cpp b/Problems/1857.cpp
@@ -0,0 +1,46 @@
+class Solution {
+public:
+  int largestPathValue(string colors, vector<vector<int>> &edges) {
+    int n = colors.size();
+    vector<unordered_map<int, int>> dp(n);
+    vector<vector<int>> adj(n);
+    vector<int> count(n, 0);
+
+    for (auto &edge : edges) {
+      adj[edge[0]].push_back(edge[1]);
+      count[edge[1]]++;
+    }
+
+    queue<int> q;
+    stack<int> st;
+
+    for (int i = 0; i < n; i++)
+      if (!count[i]) q.push(i);
+
+    while (!q.empty()) {
+      int root = q.front();
+      q.pop();
+      st.push(root);
+      for (int child : adj[root]) {
+        if (--count[child]) continue;
+        q.push(child);
+      }
+    }
+
+    for (int i = 0; i < n; i++)
+      if (count[i]) return -1;
+
+    int res = 0;
+    while (!st.empty()) {
+      int root = st.top();
+      st.pop();
+      for (int child : adj[root]) {
+        for (auto [color, count] : dp[child]) {
+          dp[root][color] = max(dp[root][color], count);
+        }
+      }
+      res = max(res, ++dp[root][colors[root]]);
+    }
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -459,6 +459,7 @@ for solving problems.
 |  1823  |   Medium   | [Find the Winner of the Circular Game](Problems/1823.cpp)                                        |
 |  1833  |   Medium   | [Maximum Ice Cream Bars](Problems/1833.cpp)                                                      |
 |  1834  |   Medium   | [Single-Threaded CPU](Problems/1834.cpp)                                                         |
+|  1857  |    Hard    | [Largest Color Value in a Directed Graph](Problems/1857.cpp)                                           |
 |  1926  |   Medium   | [Nearest Exit from Entrance in Maze](Problems/1926.cpp)                                          |
 |  1962  |   Medium   | [Remove Stones to Minimize the Total](Problems/1962.cpp)                                         |
 |  1971  |    Easy    | [Find if Path Exists in Graph](Problems/1971.cpp)                                                |