Minimum Spanning Tree
Advanced
A weighted undirected graph has n nodes and edges [a, b, w]. A spanning tree joins all nodes with n - 1 edges and no cycle. Return the smallest possible total weight of a spanning tree, or -1 if the graph is not connected. For n = 1 the answer is 0.
For n = 4 and edges = [[0, 1, 1], [1, 2, 2], [2, 3, 3], [0, 3, 10], [0, 2, 5]] the answer is 6.
Examples
Example 1
Input:
mst_weight(4, [[0, 1, 1], [1, 2, 2], [2, 3, 3], [0, 3, 10], [0, 2, 5]])
Output:
6
Example 2
Input:
mst_weight(3, [[0, 1, 4]])
Output:
-1
Constraints
1 <= n <= 1000000 <= len(edges) <= 2000001 <= w <= 10**4
Theory
Go to TheoryKeywords
dsa-sheetgraphsspanning-trees-and-components
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.