-grace-'s blog

Queries of type "Can you reach node x from node y? "
By -grace-, history, 3 years ago, In English

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.

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

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

Just in case you didn't check this advanced technique video

→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

You can compress the SCCs, each SCC will have a representative node. Do the same solution as for a DAG. When you receive a query (a, b), you change a and b to their respective representatives.

→ Reply