kanisht_09's blog

Help in Spoj problem
By kanisht_09, history, 4 years ago, In English

Please can someone help me this problem :

https://www.spoj.com/problems/BUGLIFE/

I am getting wrong answer when I m changing the color explicitly i.e before calling dfs here is the code : Your text to link here...

And i got AC when I send the color along with dfs function Your text to link here...

if u look at both the codes dont u think they are equivalent? If not please tell me which edge case am i missing? Thanks in advance :)

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

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

For easy test:

1
3 2
1 2
1 3

There you do recursion from 1. You are coloring node 1 with color 0. For neighbor 2 you change color to 1. For neighbor 3 you change color back to zero. There you recognize error although there is none.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanku very much for ur help :). Well is it possible to do this explicitly without passing into dfs? But u know passing into dfs is better :)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can use c ^= 1; as very first command in dfs and as last command before return true; (Additionally remove c ^= 1; anywhere else). Then I guess it would be fine. (You can think of giving each node the color depth & 1 and incrementing/decrementing the depth at beginning/end)

      → Reply