Блог пользователя vatsal

Help on a problem
Автор vatsal, история, 7 лет назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить