nchn27's blog

Node Reachability on a DAG
By nchn27, history, 5 years ago, In English

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?

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

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

    → Reply