Verificar a Validade de um Percurso BFS
Dada uma árvore (um grafo sem ciclos) com
n vértices e um percurso BFS (busca em largura) que indica a ordem em que os vértices foram visitados, pretende-se verificar se essa sequência de visita é plausível.O algoritmo começa sempre pelo vértice 1 e percorre os seus vizinhos sem seguir qualquer ordem específica. O teu programa deve imprimir
Yes caso este percurso seja possível para a árvore dada, ou No caso contrário.Recorda-te de que, numa árvore, existem sempre
n-1 arestas.Entrada
A primeira linha do input contém um único inteiro
n (1 ≤ n ≤ 100 000).As
n-1 linhas seguintes apresentam pares de inteiros (1 ≤ ≤ n) que representam as arestas.Na linha seguinte, surgem
n inteiros separados por espaços (1 ≤ ≤ n) que descrevem a sequência de visitas do algoritmo BFS.Saída
O programa deve imprimir
Yes se o percurso fornecido for válido, ou No caso não seja.Exemplos
Entrada | Saída |
4
1 2
1 3
2 4
1 2 3 4 | Yes |
4
1 2
1 3
2 4
1 2 4 3 | No |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB