BUGLIFE SPOJ

Here is the link to the question BUg’s Life on SPOJ [BUGLIFE][1]. I know that this is based on bfs and graph coloring. But only one thing I am unable to understand. Suppose we take a test case where number of bugs is 6 and number of interaction is 3. and the interactions are as follows.

1 2

3 4

5 6

So here how will we do a bfs? Because here we have 3 separate graphs 1->2,3->4,5->6. How can we have the link to these 3 separate graphs or anyother methods? The testcase is for exampls in general the no. of nodes of the 3 separate graphs could be many.
[1]: http://www.spoj.com/problems/BUGLIFE/

Could you explain your solution in brief? It will be difficult to understand the code. Thanks!

keep a boolean array of length the number of nodes.Once you visit a node during BFS execution mark its value true. when the BFS procedure finishes find if any node is unvisited . if yes then start BFS from that node… hope this helps :slight_smile:

by the way you can solve this question using DFS too. google for bipartiteness using DFS

Yes it helped :slight_smile: . Thanks.