Can anyone please explain me this spoj problemhttp://www.spoj.com/problems/BUGLIFE/ in more detail if possible with testcases. I am not able to understand it properly.
Its similar to graph coloring problem, where no 2 nodes should have same color.
LEt me explain the sample case-
It says that there are 3 bugs, and 3 interactions.
1 interacts with 2. This means 1 and 2 are of opposite gender. Lets assume 1 to be male and 2 to be female for simplicity.
Next, 2 interacts with 3. This means, 2 and 3 are of opposite gender as well.
Till now, we can say that Bug 1=Male, Bug2=Female, Bug3=Male, or vice versa and see that his theory holds. But now-
1 interacts with 3. 1 and 2 are of different gender, 2 and 3 are of different gender. This means that 1 and 3 must be of same gender. But they are interacting!! This means we found a case which falsifies his assumption.
Hope this clarifies the statement.
1 Like
As already mentioned in @vijju123 's answer, it is a problem of graph coloring. You have to check whether the given graph is a bipartite graph. This is because the problem wants you to check if the bugs can be divided into two genders (sets of vertices) where there is no interaction (no edge) between members of the same set.
In case you want to learn how to check if a graph is bipartite, refer this.
In case you are looking for more testcases, try this.
1 Like
Thanks a lot i now understand the problem need to work on graph coloring but yeah i will solve it.
Its actually simple if you think in terms of bipartite-ness as @dwij28 said. You can use the same logic to solve question like FILLMATR of last long very easily.
If you can give me more graph related problems in increasing order of difficulty from any platform then it we great help.