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/