Link to the question:
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