| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
Hi, everyone
Some directed graph is given. Check the graph for the uniqueness property of the path(for any two vertices v u, there is no more than one simple path with the beginning in u and the end in v). Simple path is a non-empty path whose vertices are all pairwise distinct.
Does anyone know a solution to this problem faster than running BFS from each vertex?
Not sure all cases are correct but smth like this might work:
Find strongly connected components in O(m)
BTW, What is your definition for simple paths beetween $$$v$$$ and $$$v$$$? Depending on it, my solution won't work on components that are pair of cycles with common vertex. But probably there's a fix for that as well
In this problem, I assume that a simple path is a path whose vertices are all pairwise distinct.
So is empty path from $$$v$$$ to $$$v$$$ simple? Is a cycle from $$$v$$$ to $$$v$$$ a simple path?
The path must be non-empty. If you follow the definition I gave above, the loop will not be a simple path because it will contain two vertexes v.
Well, it's not at all clear from the definition as written.
ok, anyway, it seems that you are using the most reasonable definition and with this definition the solution as written doesn't work because there are other types of "save" SCCs like mentioned two-cycles component. But it looks like you can look at cut points and block in each SCC and it each one is a cycle you are safe again.