Блог пользователя mundada

SPOJ-BUGLIFE
Автор mundada, история, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
← Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить