vatsal's blog

Help on a problem
By vatsal, history, 8 years ago, In English

I am stuck on a problem. I have read the editorial but I am not able to understand it. Can someone please give some other view on the solution or explain the editorial solution in somewhat more detailed way?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Start adding edges to DSU in order of their weight. Consider the current edge e = {u,v} with weight w.
1. If it is connecting the same component, then there would be a cycle forming. If that cycle has another edge of same weight, then this edge comes under "any". This also makes the edge that was added before with weight w to be labelled as "any". Otherwise, this edge will never come in MST, so it is labelled as "none".
2. Otherwise, if it is connecting different components, we label it currently as "at least one".
0 I hope this is correct, but will think and confirm soon.

→ Reply