Maximum Score of a Node Sequence LeetCode solution in C++

1
/*
2
    Time: O(V+E)
3
    Space: O(V+E)
4
    Tags: Graph, Set, Sorting, Greedy
5
    Difficulty: H
6
*/
7

8
class Solution {
9
 public:
10
  int maximumScore(vector<int> &scores, vector<vector<int>> &edges) {
11
    set<pair<int, int>> graph[scores.size()];
12
    for (auto edge : edges) {
13
      graph[edge[0]].insert({scores[edge[1]], edge[1]});
14
      graph[edge[1]].insert({scores[edge[0]], edge[0]});
15
      if (graph[edge[0]].size() > 3) graph[edge[0]].erase(graph[edge[0]].begin());
16
      if (graph[edge[1]].size() > 3) graph[edge[1]].erase(graph[edge[1]].begin());
17
    }
18
    int res = -1;
19
    for (auto edge : edges) {
20
      int ans = scores[edge[0]] + scores[edge[1]];
21
      for (auto node1 : graph[edge[0]]) {
22
        for (auto node2 : graph[edge[1]]) {
23
          if (node1.second != edge[0] && node1.second != edge[1] && node2.second != edge[0] &&
24
              node2.second != edge[1] && node2.second != node1.second)
25
            res = max(res, ans + node1.first + node2.first);
26
        }
27
      }
28
    }
29
    return res;
30
  }
31
};