# UVa 10462

From Algorithmist

## Contents

## 10462 - Is There A Second Way Left ?

## Summary

Given a weighted undirected graph, we have to find the second best Minimum Spanning Tree.

## Explanation

- Run a Depth-First Search or Breadth-First Search to see if the graph is connected , if no then output no way
- Now find the Minimum Spanning Tree and mark all the edges which is part of the MST.
- Ignore the edges which are part of the MST, one at a time and try to build a new MST with the available edges (be careful that the MST must be connected).
- Find the weight of MST. Among all the connected MST's find the minimum weight which is the answer . If there is no connected MST , then output no second way..

Let us take an example, let there be 5 edges in a graph G labeled 1 to 5.

let the MST considering all the edges, consists of edges 1, 3, 5. now ignore edge 1 only and consider edge 2, 3, 4, 5 to build an MST if it is possible to build an mst calculate its weight now ignore edge 3 only do the same now ignore edge 5 only and do the same among all the MST's the minimum weight one is the second best MST.

## Gotchas

- MST must be connected

## Notes

- A similar problem is UVa 10600.

## Input

4 5 4 1 2 5 3 2 5 4 2 5 5 4 5 5 3 1 2 5 3 2 5 5 4 5 5 5 1 2 5 3 2 5 4 2 5 5 4 5 4 5 6 1 0

## Output

Case #1 : No second way Case #2 : No way Case #3 : 21 Case #4 : No second way