For find out second best spanning tree is needed to first build mst tree and for each edge from mst tree flag them then again run kruskal. But how to find second best spanning tree only using union find data structure or lca. I want to know both ways :( Thanks in advance :)
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3803 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3627 |
| 4 | ecnerwala | 3584 |
| 5 | orzdevinwang | 3573 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | Radewoosh | 3542 |
| 9 | jqdai0815 | 3532 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 167 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | maroonrk | 152 |
| 5 | -is-this-fft- | 151 |
| 5 | nor | 151 |
| 7 | atcoder_official | 147 |
| 8 | TheScrasse | 146 |
| 9 | Petr | 145 |
| 10 | pajenegod | 143 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 01.07.2024 19:03:39 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
Is there yet any answer to that by using only DSU? LCA answers are widely known and appear everywhere, but I have seen nowhere anything using the DSU generated by Kruskal (without path compression of course, since path compression destroys the useful information)...
I wrote this as my homework years ago. For problem that can be solved by similar idea, you can check 1023F - Мобильная сеть and my submission 67434523.
Thanks for the PDF link.
check this submission 15317414 DSU only