Queries of type "Can you reach node x from node y? "

Revision en1, by -grace-, 2021-07-26 17:50:16

I was recently doing some CSES problems where I came across this-

A directed graph consists of n nodes and m edges. The edges are numbered 1,2,…,n. Your task is to answer q queries of the form "can you reach node b from node a?"

Link: https://cses.fi/problemset/task/2143

If the graph were acyclic, it could be done by using a bitset as DP and calculating answers from all the children's DPs. But in this problem, the graph may be cyclic.

One way of solving that came to my mind is to find all the cycles and then remove an edge from each cycle to make it acyclic. Then we proceed with the DP solution. When we have all the DPs of nodes, we can manually update the answers to all those nodes that we removed. But I am not sure if this is the intended way of solving this problem.

Is there any better way to solve it?

PS: If somebody has hints or material for CSES Advanced Techniques section, then mention it in the comments.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English -grace- 2021-07-26 17:50:16 1002 Initial revision (published)