Cod sursa(job #2473715)

Utilizator gazdac_alex@yahoo.comGazdac Alexandru Eugen [email protected] Data 14 octombrie 2019 09:23:13
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("fisier.in");
ofstream out("fisier.out");
int const maxim = 100005;
vector<int> stocare[maxim];
queue<int> coada;
int id[maxim];
int sir[maxim];
bool vizitat[maxim];
int n;

bool cmp(int a, int b){
return id[a] < id[b];
}

bool bfs(){
vizitat[1]=true;
int contor = 1;
while(!coada.empty()){
    int nod = coada.front();
    coada.pop();
    if(sir[contor]!=nod) return false;
    else contor++;
    for(size_t i=0;i<stocare[nod].size();i++){
        int vecin = stocare[nod][i];
        if(vizitat[vecin]==false){
            vizitat[vecin] = true;
            coada.push(vecin);
        }
    }
}
return  true;
}



int main(){
cin >> n;
for(int i=1;i<n;i++){
    int a,b;
    cin >> a >> b;
    stocare[a].push_back(b);
    stocare[b].push_back(a);
}
for(int i=1;i<=n;i++){
    cin >> sir[i];
    id[sir[i]]=i;
}
for(int i=1;i<=n;i++){
    sort(stocare[i].begin(),stocare[i].end(),cmp);
}
if(bfs())cout << "Yes";
else cout << "No";
return 0;}