-->
当前位置:首页 > 题库

PROGRAMMING:Judging the validity of DFS sequence

Luz5年前 (2021-05-10)题库451
Given a digraph, please judge whether the given depth first traversal sequence is legal.
For example, for the following figure
![ figure.png](~/24fea5c8-4a15-4200-bef3-a114b787d971.png)
`0 14 25 3 'and 0 25 14 3' and 3 25 14 0 'are legal DFS sequences, but 0 23 14 5' is not.
###Input format:
The first line gives the vertex number $$M $$and the number of sides $$n $, separated by spaces; Vertex labels range from 0 to $$M-1 $$. Where $$M $$does not exceed 100.
After that, $$n $$lines, each line gives each edge in the graph in the following format:
`ID1 ID2`
This represents the directed edge from vertex number 'Id1' to vertex number 'Id2'.
The next line gives the integer $$k $, which means that there are $$k $$sequences to be tested.
The next $$k $$line gives $$M $$spaces separated integers to represent the DFS sequence.
###Output format:
For each sequence to be tested, the output 'yes' means legal and' no 'means illegal.
###Input example:
```in
6 9
0 1
0 2
0 3
2 1
3 2
4 2
1 4
2 5
4 5
three
0 1 4 2 5 3
0 2 5 1 4 3
0 2 3 1 4 5
```
###Output example:
```out
Yes
Yes
No
```







answer:If there is no answer, please comment