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

this problem is to detect a loop in an undirected graph

my code —>

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

else if(x!=parent)
return true;
}
return false;
}

bool visited[V];
for(int i=0;i<V;i++)
visited[i] = false;

for(int i=0;i<V;i++)
{
if(visited[i] == false)
return true;
}

}
``````

I am getting a wrong answer

Input:
4 2
1 2
2 3

Its Correct output is:
0

1

What is this doing?

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

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

Lol, I tried printing the Adjacency list and this happened.

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.

actually, that didn’t help either

1 Like

Is your code for Directional graph or undirectional graph?

it’s for undirected graph

I am unable to find the bug

1 Like

oh no

Hey! Put the first if statement in braces.

``````if(visited[x] == false){
return true;
}
``````

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

still not working for me bro

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

public:
// 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)
}
return false;
}
};
``````

Does this work?

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

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

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

2 Likes