Undirected graph is a tree or not

#1

When we write
“if(visited[nbr]==true and parent[node]!=nbr)
{
return false;
}”

Can you explain me the second condition in if statement that why are we checking “parent[node]!=nbr”?

#2

Hey @div_yanshu07,
consider this -> 1–2–3–4
let say u started running dfs from 1 so u marked it visited then u checked for its neighbors .
it is 2 and not visited , so u call on 2, now again from u check all its neigbour (1 and 3).
here 1 is visited right? as per logic visited neigbour node means cycle right? ,but it fails here why? becuase 1 is parent node.
so here we have 2 things to consider for cycle ->
a) neighbour node must be visited
b) it should not be a parent node

#3

What will happen if I don’t check the second statement I’ll still get false rt? Because 1 is neighbour and it’s already marked true in visited array.

#4

@div_yanshu07 i have taken a case in which we are visiting all nodes from parent node that is 1 now take a case in which you are not running dfs from 1 but from 2. In this case your 1 & 3 is not visited and also your node 1 is parent. Cases like this require special attention so that’s why we are using the second if condition.
Moreover if you want an editorial for the same you can check it at https://www.geeksforgeeks.org/check-given-graph-tree/

#5

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.