prachin_roy's blog

By prachin_roy, history, 6 years ago, In English

How to solve this problem

I can't figure out the approach.Describe the approach in details please. Thanks in advance

Tags mst
  • Vote: I like it
  • -6
  • Vote: I do not like it

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

First step, sort the edges according to weight. Second step, sort the query. Third step firstly takes the higher or equal weighted edges of the highest value of the query. then connect them through disjoint set union. here you can find the solution for the highest value of the query. In this way, by adding the edges according to the value of decreasing query you will get all solutions of the query.