aboutsummaryrefslogtreecommitdiff
path: root/largest_colour_value_graph.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'largest_colour_value_graph.cpp')
-rw-r--r--largest_colour_value_graph.cpp87
1 files changed, 0 insertions, 87 deletions
diff --git a/largest_colour_value_graph.cpp b/largest_colour_value_graph.cpp
deleted file mode 100644
index 984f472..0000000
--- a/largest_colour_value_graph.cpp
+++ /dev/null
@@ -1,87 +0,0 @@
-// 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(int) & 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(int) & 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(int) 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(int) e1 = {{0, 1}, {0, 2}, {2, 3}, {3, 4}};
- vvd(int) e2 = {{0, 0}};
- printf("%d\n", obj.largestPathValue("abaca", e1)); // expect: 3
- printf("%d\n", obj.largestPathValue("a", e2)); // expect: -1
-}