damon2598's blog

By damon2598, history, 5 years ago, In English

I was trying to solve this problem : http://codeforces.com/problemset/problem/1037/D (Valid BFS) . My submission is :http://codeforces.com/contest/1037/submission/45684523

My method : I am storing parent of each node (using bfs) . then , I am checking that is the new bfs following the order policy , using a queue . The code is neat and small . Please someone help me , I want to know where my algorithm is wrong .

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  1. Your algorithm will push leaf nodes to the queue and may check if parent[arr[i]]==<leaf node>.
  2. You need to push arr[i] (if it's not a leaf node) regardless if parent[arr[i]] is equal to par or not.
  3. I suggest checking if arr[0] == 1, setting par to 0 and pushing node 1 since your program may try to pop an empty queue.
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the correction . I found a mistake , Your 2nd recommendation is correct , I was wrong there . Thanks.

»
5 years ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

A possible solution of this problem is to iterate through the required sequence ai, for 1 ≤ i ≤ n, after pushing the root node 1 to the queue, and marking it as visited. In iteration i, if the queue is not empty and its front is not equal to ai, then the answer is "No". Otherwise, the front ai is popped and its unvisited neighbors if exist are pushed to the queue in the same order in which they appear in the sequence a, and marked as visited. If all nodes are visited and the queue is empty after this loop, then the answer is "Yes". Otherwise, the answer is "No".

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

    Theoretically , I have done the same thing. I am checking whether the edges in the new bfs traversal are valid or not . For example , if there is an edge from 1 to 6 in the graph , then the bfs sequence should also have edge from 1 to 6. Similarly , If for all child nodes , parent is same as it was in the question , then I will print 'Yes'.