PreviousNext
Coding/Graphs and trees

Maximum spanning tree weight

Write codeMedium25 min

Your task

Given a connected-or-not undirected weighted graph with n nodes (0..n-1) and edges [w, u, v] (weight first), return the total weight of a maximum spanning tree: a spanning tree maximizing the sum of chosen edge weights. If the graph is not connected (no spanning tree exists), return -1. A single node with no edges has weight 0. Constraints: 1 <= n <= 1000.

Examples

max_spanning_tree_weight(n: int, edges: list[list[int]]) -> int
Example 1
Inputmax_spanning_tree_weight(3, [[1, 0, 1], [2, 1, 2], [3, 0, 2]])
Output5