Cycle Detection DFS - AC on CodeChef, WA on SPOJ

Why does this code get accepted on CodeChef but NOT on SPOJ?
My solution: https://ide.geeksforgeeks.org/RSwUPkea6K
SPOJ: https://www.spoj.com/problems/PT07Y/
CC: https://www.codechef.com/problems/PD31

1 Like

SPOJ usually has stronger and trickier test cases than Codechef.
If you give this input to your code (which is valid according to constraints):

3 2
1 2
1 2

It should output NO but it gives YES. I would make a change to your DFS by considering the case when neighbor vertex is already visited (taking care of the parent of s in the DFS Tree, since those 2 nodes can’t make a cycle, I added the parameter p to be the parent of s in the DFS Tree).

if(*i == p) continue;
if(visited[*i]) return true; // Since is an edge joining two visited nodes
else Do what you have for this case

When using the former way you don’t need to check if s is visited or not before checking its neighbors :smiley:

The last change I considered is that you were reading m edges but for you m is the number of vertices.

AC Code: https://ide.geeksforgeeks.org/xmyOeERXvK