leetcode

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 };