aboutsummaryrefslogtreecommitdiff
path: root/largest_colour_value_graph.cpp
blob: 984f4722621d3cfe02a4f6ca452c95b2dd0fbf99 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
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(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
}