| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
You are given a DAG with N nodes and Q queries asking if node b can be reached from node a. Can this problem be solved for the likes of N = 10^5 and Q = 10^5?
Also I think if we are given a general directed graph, the problem can be turned into one on a DAG if we do SCC's?
It can be solved in O(n^2/64): Invent dp[i][j] — 1 if node j can be reached from node i, and 0 if not. We will calculate this dp using dfs — node j can be reached from node i only if i=j or j can be reached from one of sons (sons of vertex i). If we store dp like bitset, we calculate it in O(n^2/64):
I think this works? EDIT: This is really stupid. Note to self: successor graphs and DAGs are not the same :/
Topo sort and precompute successor values for powers of two for each vertex of the DAG in O(n log n), as in competitive programmer's handbook (pg. 165 as of now).
Then find the further back of node a and b and binary search on its successors to determine if b is a successor.
Complexity: O(n log^2 n)
This doesn’t work since if two nodes are on the same level then they can appear in any order in the toposort.