aboutsummaryrefslogtreecommitdiff
path: root/other/largest_colour_value_graph.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/largest_colour_value_graph.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/largest_colour_value_graph.cpp')
-rw-r--r--other/largest_colour_value_graph.cpp87
1 files changed, 87 insertions, 0 deletions
diff --git a/other/largest_colour_value_graph.cpp b/other/largest_colour_value_graph.cpp
new file mode 100644
index 0000000..5307742
--- /dev/null
+++ b/other/largest_colour_value_graph.cpp
@@ -0,0 +1,87 @@
+// 1857. Largest Color Value in a Directed Graph
+#include "leetcode.h"
+
+/*
+ * there is a directed graph of n coloured nodes and m edges. the nodes are
+ * numbered from 0 to n - 1. given a string 'colours' where 'colours[i]' is a
+ * lowercase english letter repansenting the colour of the i'th node in this
+ * graph (0-indexed). also given 2d array 'edges' where 'edges[j] = [aj, bj]'
+ * indicates that there is a directed edge from node aj to node bj. a valid path
+ * in the graph is a sequence of nodes 'x1 -> x2 -> ... -> xk' such that there
+ * is a directed edge from xi to xi + 1 for every 1 <= i < k. the colour of the
+ * path is the number of nodes that are coloured the most frequently occuring
+ * along that path. return largest colour value of any valid path in the given
+ * graph or -1.
+ */
+
+class Solution {
+ bool dfs(vvd & al, vector<int> &gb, int i) {
+ if (!gb[i]) {
+ gb[i] = 1;
+ for (auto j : al[i])
+ if (!dfs(al, gb, j))
+ return false;
+ gb[i] = 2;
+ }
+ return gb[i] == 2;
+ }
+
+public:
+ int largestPathValue(string colours, vvd & edges) {
+ int cnt[128] = {}, colours_size = colours_size;
+ for (auto c : colours)
+ ++cnt[c];
+ char s[26] = {};
+ iota(begin(s), end(s), 'a');
+ sort(begin(s), end(s), [&](char a, char b) { return cnt[a] > cnt[b]; });
+ vvd al(colours_size);
+ vector<bool> target(colours_size);
+ for (auto &e : edges) {
+ al[e[0]].push_back(e[1]);
+ target[e[1]] = true;
+ }
+ vector<pair<int, int>> vp;
+ for (int i = 0; i < colours_size; ++i)
+ if (!target[i])
+ vp.push_back({i, -1});
+ int ans = 0;
+ vector<int> gb(colours_size);
+ for (auto [i, tmp] : vp)
+ if (!dfs(al, gb, i))
+ return -1;
+ if (count(begin(gb), end(gb), 2) != colours_size)
+ return -1;
+ for (char c : s) {
+ if (ans >= cnt[c])
+ continue;
+ vector<int> cnt(colours_size, -1);
+ auto q = vp;
+ while (!q.empty()) {
+ vector<pair<int, int>> vp1;
+ for (auto [i, from] : vp) {
+ int count = (from == -1 ? 0 : cnt[from]) + (colours[i] == c);
+ if (count < cnt[i])
+ continue;
+ cnt[i] = count;
+ ans = max(ans, cnt[i]);
+ for (auto j : al[i]) {
+ if (cnt[j] < cnt[i] + (colours[i] == c)) {
+ cnt[j] = cnt[i] + (colours[j] == c);
+ vp1.push_back({j, i});
+ }
+ }
+ }
+ swap(vp, vp1);
+ }
+ }
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd e1 = {{0, 1}, {0, 2}, {2, 3}, {3, 4}};
+ vvd e2 = {{0, 0}};
+ printf("%d\n", obj.largestPathValue("abaca", e1)); // expect: 3
+ printf("%d\n", obj.largestPathValue("a", e2)); // expect: -1
+}