Minimum spanning tree variation [HELP]

Revision en1, by Aritra741, 2019-08-09 20:19:21

Given a graph with n(<=100) vertices and m( <=n(n-1)/2 ) edges, you are asked to find a spanning tree with the minimum difference between the biggest and the smallest edge of the tree.

The problem can be found Here (UVA 1395). I can't figure out an efficient way to solve this. Any kind of help is appreciated.

Tags mst, dsu

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Aritra741 2019-08-10 09:20:41 138
en1 English Aritra741 2019-08-09 20:19:21 457 Initial revision (published)