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?
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/04/2024 21:14:03 (i1).
Desktop version, switch to mobile version.
Supported by
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.