Блог пользователя nchn27

Node Reachability on a DAG
Автор nchn27, история, 5 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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):

→ Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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)

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    This doesn’t work since if two nodes are on the same level then they can appear in any order in the toposort.

    → Ответить