Bipartite Graph Check

#1

What is wrong in my code? It is not giving correct output.

#2

@avijuneja2007 you have not applied dfs correctly. Just do the standard way of doing the dfs.
If you are sure about dfs then i will recommend you to rewatch the dfs video lecture.

After trying this if you are not able to resolve this then let me know, i will correct your code or tell you what to do.

#3

I am still not able to find what is wrong. Can you please do the modification !!

#4

@avijuneja2007
I have done detailed commenting for the changes, have a look at it https://ide.codingblocks.com/s/239193

Also if you still have some doubt in understanding dfs then i will recommend you to rewatch Depth first Search and cycle detection using dfs videos.
If you have some other doubt you can ask.

1 Like
#5

@avijuneja2007 if you understand it now then please mark this doubt as resolved.

#6

I understood 95% of your code. I am just confused about the condition parent!=child. Can you give an example to explain this condition?

#7

It is just for checking whether the node which you are visiting as a child is it parent or not.

Take a small example of edges 1----2 and 2----3.
So when we call DFS at 1 then it will visit 2 recursively, then from 2 it has one child as 3 and one child as 1 also(because graph is undirected), so it may visit 1 again from 2. But we don’t need to visit 1 when we are at 2 because it is already traversed.

1 Like