I was asked to solve two problems. There are really good problems so I would like to discuss them here.

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.

Hello everyone, I am having a problem in solving this problem from CSES problem set. I could not find any explanation for this problem.

I solved the "Movie Festival" problem which is easier version of this one by simply sorting the intervals by end time and then iterating over all the intervals and comparing begin time of each interval with previous interval's end. But that approach will give O(n^2) in this problem.

I was thinking of applyng Mo's to use the same approach but could not proceed.

Any help would be appreciated. Thanks and keep coding!!