mundada's blog

SPOJ-BUGLIFE
By mundada, history, 8 years ago, In English

Link to problem. It would be very helpful if someone could suggest why my solution gives the wrong answer. I have understood that we have to find whether the graph is bipartite or not, but still I am getting wrong answers. Any help would be appreciated.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
8 years ago, # |
  Vote: I like it +24 Vote: I do not like it

I didn't choose the bug life, the bug life chose me; I can't shake off the bugs of my code.

→ Reply
»
8 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

1

4 4

1 4

2 3

3 4

2 4

Your code print 'No suspcious bugs found' but it should print 'Suspcious bugs found', because 2->3->4->2 is an odd-length cycle, and so the graph is not bipartite. Your mistake is here:

"if visited[v] == 0: bipartite(adj, color, v)"

You have to return -1 if at some time bipartite returned -1, not just call it. This way:

"if visited[v] == 0: if bipartite(adj, color, v) == -1: return -1"

The reason is simple, if you return -1 after the first call, it won't return the answer. Your code did right in the sample tests because it returns -1 in the first call. http://ideone.com/By2nVd

I fix it, but now it gaves TLE.

→ Reply