| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Let's you have a graph with n nodes and m bi-directional edges. (n, m <= 1e5). How would I get the cycles in this graph in an efficient way using DFS.
BTW, I've linked an image where I drew what I thought is a cycle. If it's not a cycle, please tell me what a cycle actually is.
Auto comment: topic has been updated by tgp07 (previous revision, new revision, compare).
Auto comment: topic has been updated by tgp07 (previous revision, new revision, compare).
Auto comment: topic has been updated by tgp07 (previous revision, new revision, compare).
I can't open your link. I'm not sure what you mean 'cycle'.
But actually for a graph, there can be 2 ^ v cycles.
Auto comment: topic has been updated by tgp07 (previous revision, new revision, compare).
A graph contains a cycle if during a graph traversal, we find a node whose neighbor (other than the previous node in the current path) has already been visited.
Do you know how to go about getting the lengths of a cycle?
The length of the cycle is the difference in heights of those two nodes on the DFS tree, plus one (for the edge going back up the DFS tree)
Thanks, this makes sense.