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 .
Thanks for the correction . I found a mistake , Your 2nd recommendation is correct , I was wrong there . Thanks.
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".
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'.