Detect cycle in undirecred graph

#1

https://practice.geeksforgeeks.org/problems/detect-cycle-in-an-undirected-graph/1

Can you please tell the error in my code. All the test cases I am giving on my own, it is giving the correct answer, can you give me a test case that this code misses.
As told by sir I can see I am missing another recursive call. But I want to know the test case that this code won’t pass.

My code is : https://ide.codingblocks.com/s/244701

#2

someone pls reply.

vis[sv] = true;
for(auto x : g[sv]){
if(vis[x] == false){
vis[x] = true;
check(g,vis,x,sv); // if I don’t store it’s value in variable and return that.
}
else if( x != prt ){
return true;
}
}
return false;

which test case this code will miss. See my commented line

#3

hello @amitqy
a)
image
this line should be
image
because if any component has cycle then we should return true

b)
image
if value return by this function call is true then return true
image

check ur corrected code here ->

#4

I was aware of that correction, can you me a test case that misses that condition, coz I wasn’t able to find one. The input format is :-
" The first line of the input contains an integer ‘T’ denoting the number of test cases. Then ‘T’ testcases follow. Each testcase consists of two lines. Description of testcases are as follows: The First line of each testcase contains two integers ‘N’ and ‘M’ which denotes the no of vertices and no of edges respectively. The Second line of each test case contains ‘M’ space separated pairs u and v denoting that there is a bidirectional edge from u to *v .

#5

test for this
1->2
2->3
3->1

#6

giving correct answer in this test case

#7

test for this
1
5 4
1 2
2 3
3 4
4 2

#8

ya ok, can you tell why it didn’t work ?I am currently finding that out

#9

because of this only
image

this is not returning true to its parent

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.