Below is the question link. https://cses.fi/problemset/task/1197 In this question I was thinking to get all cyclic paths and then go through all of them to get if any path has a negative value, if there is such a value then just print it and break the loop there itself. But I am having problem in printing all cyclic paths. :(
Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3880 |
| 2 | jiangly | 3669 |
| 3 | ecnerwala | 3654 |
| 4 | Benq | 3627 |
| 5 | orzdevinwang | 3612 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | jqdai0815 | 3532 |
| 9 | Radewoosh | 3522 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | adamant | 156 |
| 4 | maroonrk | 153 |
| 5 | -is-this-fft- | 148 |
| 5 | atcoder_official | 148 |
| 5 | SecondThread | 148 |
| 8 | Petr | 147 |
| 9 | nor | 144 |
| 9 | TheScrasse | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.07.2024 04:21:21 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
Use Bellman-Ford
My first thought was Bellman-Ford but how do you print a negative cyclic path using Bellman-Ford and other issue was it has a huge time complexity. Do you have some other ideas?
The code in the link above prints the path, and the complexity is $$$O(N*M)$$$ where N is number of vertex and M number of edges. This will work for the given constraints.
i can't wrap my head around the parents, can you help me understand why parents will always lead to the right path?
We basically to a DFS in the graph, so each vertex has some parent, which is the vertex visited just before the current one.
In the implementation x is the vertex visited in nth loop. Since the longest possible cycle includes only n vertex, a vertex that changes in the nth loop is allways one on a negative cycle. Since in the DFS we had allways set p[v]="parent of v", p[i]->i is exactly such cycle.
Note that there is not "the right path", since there could be more than one such cycle in the graph, we just have to find any one.
I still don't understand, how are you referring it similar to a DFS? if i am not wrong, in bellman Form, we really don't follow edges in any order right? it might be possible that we are taking some other path's to edge to point to one of node in our actual path ( i know there can be multiple ), and it could mess up all the negative cycle. why is this not happing in the above mentioned solution? is there any more indepth reference for this ? i am having hard time grasping it :(.