Is this a DFS traversal? P52199
You are given an undirected graph with n vertices (numbered from 0) and m edges, and a sequence of k vertices. Can the sequence be the result of a Depth First Search traversal of the graph starting at 0? Please remember that a DFS explores as far as possible along each branch, and backtracks only when the current vertex has already been explored. The neighbours of each vertex can be visited in any order.
Input
Input consists of several cases, each one with n and m, followed by the m edges x y, followed by k, followed by k different vertices between 0 and n−1. Assume 1 ≤ n ≤ 104, 0 ≤ m ≤ 5n, x ≠ y, that there are no repeated edges, and 1 ≤ k ≤ n.
Output
For every case, print the right answer “yes” or “no”.
Input
8 5 5 0 4 5 0 2 6 1 5 7 5 0 2 5 7 4 4 4 0 1 1 2 2 3 3 0 4 0 1 3 2 4 4 0 2 2 3 3 1 1 2 4 0 2 3 1
Output
yes no yes
- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++