Link to the question:

https://www.codechef.com/LRNDSA08/problems/ACM14KG3

I ended up doing this differently and getting AC, but I’m getting WA on my original solution and I can’t seem to figure out why.

My original logic was instead of perform DFS on each character which I thought would be expensive, use DFS once and store a boolean in a 2D matrix indicating whether there’s a path from node s -> t. With this information, I can use constant time queries to determine whether there’s a path from one character to another.

I’ve tried testing my implementation on different graphs, but it works on all of the things I could come up with.

Here’s my submission: https://www.codechef.com/viewsolution/36146830