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?
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?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 173 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 160 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
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.