In this guide, you will get 3547. Maximum Sum of Edge Values in a Graph LeetCode Solution with the best time and space complexity. The solution to Maximum Sum of Edge Values in a Graph problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Sum of Edge Values in a Graph
You are given an undirected graph of n nodes, numbered from 0 to n – 1. Each node is connected to at most 2 other nodes.
The graph consists of m edges, represented by a 2D array edges, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi.
You have to assign a unique value from 1 to n to each node. The value of an edge will be the product of the values assigned to the two nodes it connects.
Your score is the sum of the values of all edges in the graph.
Return the maximum score you can achieve.
Example 1:
Input: n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6]]
Output: 130
Explanation:
The diagram above illustrates an optimal assignment of values to nodes. The sum of the values of the edges is: (7 * 6) + (7 * 5) + (6 * 5) + (1 * 3) + (3 * 4) + (4 * 2) = 130.
Input: n = 6, edges = [[0,3],[4,5],[2,0],[1,3],[2,4],[1,5]]
Output: 82
Explanation:
The diagram above illustrates an optimal assignment of values to nodes. The sum of the values of the edges is: (1 * 2) + (2 * 4) + (4 * 6) + (6 * 5) + (5 * 3) + (3 * 1) = 82.
Constraints:
1 <= n <= 5 * 104
m == edges.length
1 <= m <= n
edges[i].length == 2
0 <= ai, bi < n
ai != bi
There are no repeated edges.
Each node is connected to at most 2 other nodes.
Complexity Analysis
Time Complexity: O(|V| + |E|)
Space Complexity: O(|V| + |E|)
3547. Maximum Sum of Edge Values in a Graph LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
3547. Maximum Sum of Edge Values in a Graph LeetCode Solution in Java
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);
}
} // code provided by PROGIEZ
3547. Maximum Sum of Edge Values in a Graph LeetCode Solution in Python
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 # code by PROGIEZ
