What mistake am i doing in this graph problem? Help please

general
, , ,
1

this problem is to detect a loop in an undirected graph

problem link :- Detect cycle in an undirected graph | Practice | GeeksforGeeks

my code —>

```
bool cycle(vector<int> adj[], int s, bool visited[], int parent)
{
    visited[s] = true;
    for(auto x:adj[s])
    {
        if(visited[x] == false)
            if(cycle(adj,x,visited,s)==true)
                return true;
                
        else if(x!=parent)
            return true;
    }
    return false;
}

bool isCycle(int V, vector<int>adj[]){
    bool visited[V];
   for(int i=0;i<V;i++)
        visited[i] = false;
  
  
  for(int i=0;i<V;i++)
  {
      if(visited[i] == false)
            if(cycle(adj,i,visited,-1) == true);
                return true; 
  }

}
2

I am getting a wrong answer

Input:
4 2
1 2
2 3

Its Correct output is:
0

And Your Code’s output is:
1

3

someone help please :joy:

4

What is this doing?

5

If an adjacent vertex is visited and is not parent of current vertex, then there exists a cycle in the graph.

6

if(cycle(adj,i,visited,-1) == true);

Please remove ; from the end of this line, otherwise, your function will always return true irrespective of if condition

7

Lol, I tried printing the Adjacency list and this happened.
Screenshot from 2021-03-20 11-50-12

If you don’t understand what it is, here is the explanation.

What we think the graph is:

0 → null
1 → 2
2 → 3
4 → null

What actually the graph is:

0 → null
1 → 2
2 → 1 → 3
3 → 2

As you can see, there is a cycle. I guess it’s the fault of code stubs. The edges are bi-directional.

Oh, I have mistaken, it’s Undirected graph. So, I should change my approach.

8

actually, that didn’t help either :neutral_face:

1 Like
9

Is your code for Directional graph or undirectional graph?

10

it’s for undirected graph

11

I am unable to find the bug :slightly_frowning_face:

1 Like
12

:frowning: oh no

13

Hey! Put the first if statement in braces.

if(visited[x] == false){
         if(cycle(adj,x,visited,s)==true)
                return true;
}
14

no bro, since they are indented properly, i think it’s one and the same thing

16

still not working for me bro

17 
bool cycle(vector<int> adj[], int s, bool visited[], int parent){
    visited[s] = true;
    for(auto& x:adj[s])
    {
        if(visited[x] == false){
            if(cycle(adj,x,visited,s)==true)
                return true;
        }
        else if(x!=parent){
            return true;
        }
    }
    return false;
}
    
public:
	bool isCycle(int V, vector<int>adj[]){
	    // Code here
	    bool visited[V];
       for(int i=0;i<V;i++)
            visited[i] = false;
      
      
      for(int i=0;i<V;i++)
      {
          if(visited[i] == false)
                if(cycle(adj,i,visited,-1) == true) return true; 
      }
      return false;
	}
};

Does this work?

18

YES YES that worked… thanks
But I have some doubts

why did the indented nested “for” loop didn’t work well ? Usually I don’t give brackets if it has a single line inside it and it works well.

return false line at the end also made the difference :joy:

19

So I am not sure but what happens is that the else statement belongs to the innermost if. Now since you weren’t enclosing the outermost if in brackets the else statement was being used when the inner if failed. For that reason, I didn’t put the nested if-statement of the isCycle function in braces since it had no else to work with

" The Java programming language, like C and C++ and many programming languages before them, arbitrarily decrees that an else clause belongs to the innermost if to which it might possibly belong."
source: Chapter 14. Blocks and Statements

1 Like
20

ohh thanks a lot, I didn’t know this before…
RESPECT +100

2 Likes