3547. Maximum Sum of Edge Values in a Graph

• Time: $O(|V| + |E|)$
• Space: $O(|V| + |E|)$

C++JavaPython

class Solution {
 public:
  long long maxScore(int n, vector<vector<int>>& edges) {
    long ans = 0;
    vector<vector<int>> graph(n);
    vector<int> cycleSizes;  // components where all nodes have degree 2
    vector<int> pathSizes;   // components that are not cycleSizes
    vector<bool> seen(n);

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      graph[u].push_back(v);
      graph[v].push_back(u);
    }

    for (int i = 0; i < n; ++i) {
      if (seen[i])
        continue;
      const vector<int> component = getComponent(graph, i, seen);
      const bool allDegree2 = ranges::all_of(
          component, [&graph](int u) { return graph[u].size() == 2; });
      if (allDegree2)
        cycleSizes.push_back(component.size());
      else if (component.size() > 1)
        pathSizes.push_back(component.size());
    }

    for (const int cycleSize : cycleSizes) {
      ans += calculateScore(n - cycleSize + 1, n, /*isCycle=*/true);
      n -= cycleSize;
    }

    ranges::sort(pathSizes, greater<>());

    for (const int pathSize : pathSizes) {
      ans += calculateScore(n - pathSize + 1, n, /*isCycle=*/false);
      n -= pathSize;
    }

    return ans;
  }

 private:
  vector<int> getComponent(const vector<vector<int>>& graph, int start,
                           vector<bool>& seen) {
    vector<int> component = {start};
    seen[start] = true;
    for (int i = 0; i < component.size(); ++i) {
      const int u = component[i];
      for (const int v : graph[u]) {
        if (seen[v])
          continue;
        component.push_back(v);
        seen[v] = true;
      }
    }
    return component;
  }

  long calculateScore(int left, int right, bool isCycle) {
    deque<long> window = {right, right};
    long score = 0;
    for (int value = right - 1; value >= left; --value) {
      const long windowValue = window.front();
      window.pop_front();
      score += windowValue * value;
      window.push_back(value);
    }
    return score + window[0] * window[1] * isCycle;
  }
};

class Solution {
  public long maxScore(int n, int[][] edges) {
    long ans = 0;
    List<Integer>[] graph = new List[n];
    List<Integer> cycleSizes = new ArrayList<>(); // components where all nodes have degree 2
    List<Integer> pathSizes = new ArrayList<>();  // components that are not cycleSizes
    boolean[] seen = new boolean[n];

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      graph[u].add(v);
      graph[v].add(u);
    }

    for (int i = 0; i < n; ++i) {
      if (seen[i])
        continue;
      List<Integer> component = getComponent(graph, i, seen);
      final boolean allDegree2 = component.stream().allMatch(u -> graph[u].size() == 2);
      if (allDegree2)
        cycleSizes.add(component.size());
      else if (component.size() > 1)
        pathSizes.add(component.size());
    }

    for (final int cycleSize : cycleSizes) {
      ans += calculateScore(n - cycleSize + 1, n, true);
      n -= cycleSize;
    }

    Collections.sort(pathSizes, Collections.reverseOrder());

    for (final int pathSize : pathSizes) {
      ans += calculateScore(n - pathSize + 1, n, false);
      n -= pathSize;
    }

    return ans;
  }

  private List<Integer> getComponent(List<Integer>[] graph, int start, boolean[] seen) {
    List<Integer> component = new ArrayList<>(List.of(start));
    seen[start] = true;
    for (int i = 0; i < component.size(); ++i) {
      final int u = component.get(i);
      for (final int v : graph[u]) {
        if (seen[v])
          continue;
        component.add(v);
        seen[v] = true;
      }
    }
    return component;
  }

  private long calculateScore(int left, int right, boolean isCycle) {
    Deque<Long> window = new ArrayDeque<>();
    window.offerLast((long) right);
    window.offerLast((long) right);
    long score = 0;
    for (int value = right - 1; value >= left; --value) {
      final long windowValue = window.pollFirst();
      score += windowValue * value;
      window.offerLast((long) value);
    }
    return score + window.peekFirst() * window.peekLast() * (isCycle ? 1 : 0);
  }
}

class Solution:
  def maxScore(self, n: int, edges: list[list[int]]) -> int:
    ans = 0
    graph = [[] for _ in range(n)]
    cycleSizes = []  # components where all nodes have degree 2
    pathSizes = []  # components that are not cycleSizes
    seen = set()

    for u, v in edges:
      graph[u].append(v)
      graph[v].append(u)

    for i in range(n):
      if i in seen:
        continue
      component = self._getComponent(graph, i, seen)
      if all(len(graph[u]) == 2 for u in component):
        cycleSizes.append(len(component))
      elif len(component) > 1:
        pathSizes.append(len(component))

    for cycleSize in cycleSizes:
      ans += self._calculateScore(n - cycleSize + 1, n, True)
      n -= cycleSize

    for pathSize in sorted(pathSizes, reverse=True):
      ans += self._calculateScore(n - pathSize + 1, n, False)
      n -= pathSize

    return ans

  def _getComponent(
      self,
      graph: list[list[int]],
      start: int,
      seen: set[int],
  ) -> list[int]:
    component = [start]
    seen.add(start)
    for u in component:
      for v in graph[u]:
        if v in seen:
          continue
        component.append(v)
        seen.add(v)
    return component

  def _calculateScore(self, left: int, right: int, isCycle: bool) -> int:
    window = collections.deque([right, right])
    score = 0
    for value in range(right - 1, left - 1, -1):
      windowValue = window.popleft()
      score += windowValue * value
      window.append(value)
    return score + window[0] * window[1] * isCycle