Have a DAG and we want that for each node v find the number of vertex that existence a path from v to that vertexes
for n <= 1e5
Have a DAG and we want that for each node v find the number of vertex that existence a path from v to that vertexes
for n <= 1e5
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 134 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
| Название |
|---|



I think simple traversing can helpful.
That is Good but the order is O(n^2);
Not really because you are using the adjacency-list representation of the graph.
Actually the answer is just to run DFS/BFS on that node and see how many nodes are visited in the process.
Complexity O(E + V)
That not for each vertex
Then you can find the condensation graph into SCC and run DFS to find the answer recursively. Complexity doesn't change
I have modified the code to make it run in O(n)
Can we really compute the number of vertices that can be reached from vertex v with this algorithm?
I think this graph is a counterexample.
(UPD: Sorry, the number with the red color font actually should be 6)
You can use a bit-parallel strategy.
Assuming bit operations for one word is O(1), and let |word| the word-length of your machine, and then the time complexity would be O(NM/|word|). The memory complexity to store the reachability can be O(N*|word|) if you only care about the reachability from |word| vertices at the same time.
In other words, in today's 64-bit environment, it's nearly 64x faster than the naive algorithm to check the reachability from each vertex to all vertices one by one.