Verifica della validità di un attraversamento BFS
Dato un albero (un grafo privo di cicli) con
n vertici e un attraversamento BFS che riporta l’ordine in cui i vertici sono stati visitati, si desidera controllare se tale ordine di visita è davvero possibile.L’algoritmo inizia sempre dal vertice 1 e visita i vicini senza seguire alcun ordine specifico. Il programma deve stampare
Yes se la sequenza di visita è compatibile con l’albero fornito, altrimenti deve stampare No.Si ricorda inoltre che un albero presenta sempre
n-1 archi.Input
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ 100 000).Le successive
n-1 righe contengono coppie di interi (1 ≤ ≤ n) che rappresentano gli archi.La riga seguente contiene
n interi separati da spazio, (1 ≤ ≤ n), che indicano la sequenza di visita del BFS.Output
Il programma deve stampare
Yes se lo scenario descritto è possibile, altrimenti No.Esempi
Ingresso | Uscita |
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