Question on Bipartite graph

Revision en2, by XNight_KingX, 2019-07-22 21:42:50

This Question: https://codeforces.com/contest/687/problem/A is requiring me to check if the graph is bipartite, but my code https://codeforces.com/contest/687/submission/57552054 is failing on this test case : 10 9

2 5

2 4

2 7

2 9

2 3

2 8

2 6

2 10

2 1

my output:

1

2

9

1 5 4 7 9 3 8 6 10

according to author solution ans is -1 that is graph is not bipartite. Why is the above graph not bipartite? we can clearly divide it into two disjoint set of vertices.

I have another Question: which one is better for bipartition check BFS or DFS? I think DFS is better but not able to Deduce this intuition clearly? can you help me with that. Noobie here, pls go less hard>> :)

Tags #graph, #bipartite, #dfs and similar, #bfs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English XNight_KingX 2019-07-22 22:15:46 544
en3 English XNight_KingX 2019-07-22 21:43:53 4
en2 English XNight_KingX 2019-07-22 21:42:50 30
en1 English XNight_KingX 2019-07-22 21:41:50 724 Initial revision (published)