A road network contains multiple possible roads and their building costs. If you keep only the roads that belong to a minimum spanning tree and remove all others, how much cost do you save? Pattern focus: Minimum Spanning Tree. The answer is total edge cost minus MST cost.
n = number of cities, edges = undirected weighted roads [u, v, w]
total savings after keeping only the minimum spanning tree
Example 1:
Input:
n = 4 edges = [[1,2,1],[2,3,2],[3,4,3],[1,4,4]]
Output:
4
Explanation:
Total cost is 10 and MST cost is 6, so savings are 4.
Example 2:
Input:
n = 5 edges = [[1,2,2],[2,3,3],[3,4,1],[4,5,4],[1,5,10],[2,5,6]]
Output:
16
Explanation:
Total cost is 26 and MST cost is 10, so savings are 16.
Example 3:
Input:
n = 3 edges = [[1,2,5],[2,3,7]]
Output:
0
Explanation:
The graph is already a tree, so there is no removable road cost.