I was trying to solve this problem.
I could only figure out the naive solution. (DFS from each vertex) I think I have encountered similar problems before but I couldn't solve them either. How do I solve this kind of problem?
→ Обратите внимание
До соревнования
Refact.ai Match 1 (Codeforces Round 985)
10:07:21
Зарегистрироваться »
Refact.ai Match 1 (Codeforces Round 985)
10:07:21
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 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 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 09.11.2024 07:27:41 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
Is there an English problem statement?
Oops, sorry I uploaded the wrong version. The link is updated now.
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
The problem isn't that hard.
My idea is to compress the graph into strongly connected components. Then the new graph will be DAG. Lets call a LEAF every vertex with 0 outcoming edges. The value will be equal to the minimal size of a leaf (number of vertexes in leaf). This can be simply solved just by finding the leaves.
Overall complexity: O(N+M).
I see. I was thinking of SCC but didn't know how to proceed. I never used the trick of compressing SCCs into single vertices before.