SHARE
TWEET

Untitled

a guest Jan 24th, 2020 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool rpta;
  5.  
  6. void bfs(vector<vector<int>> v, queue<int> q, vector<int> rec, int ini){
  7.     rec[ini] = 1;
  8.     q.push(ini);
  9.     while(q.size()!=0){
  10.         int n = q.front();
  11.         q.pop();
  12.         vector<int> aux;
  13.         vector<int> aux2;
  14.         for(int i = 0; i < v[n].size(); i++){
  15.             if(rec[v[n][i]]==0){
  16.                 rec[v[n][i]] = 1;
  17.                 aux.push_back(v[n][i]);
  18.             }
  19.         }
  20.         for(int i = 0; i < aux.size();i++){
  21.                 int aa = q.front();
  22.                 aux2.push_back(aa);
  23.                 q.pop();
  24.         }
  25.         for(int i = 0; i< aux2.size();i++){
  26.             bool found = false;
  27.             for(int j = 0; j < aux.size();j++){
  28.                 if(aux2[i]==aux[j]){
  29.                     found = true;
  30.                 }
  31.             }
  32.             if(!found){
  33.                 rpta = false;
  34.                 return;
  35.             }
  36.         }
  37.         for(int i = 0; i < aux2.size();i++){
  38.             q.push(aux2[i]);
  39.         }          
  40.     }
  41. }
  42.  
  43. int main(){
  44.     int n,x,y,aux;
  45.     rpta = false;
  46.     cin >> n;
  47.     vector<vector<int>> v(n);
  48.     queue<int> valid;
  49.     vector<int> rec(n,0);
  50.     queue<int> q;
  51.     for(int i = 1; i < n; i++){
  52.         cin >> x >> y;
  53.         v[x].push_back(y);
  54.     }
  55.     for(int i = 0; i < n; i++){
  56.         cin >> aux;
  57.         valid.push(aux);
  58.     }
  59.     int ini = valid.front();
  60.     valid.pop();
  61.     bfs(v,q,rec,ini);
  62.     rpta ? cout << "Yes" : cout << "No";
  63.     return 0;
  64. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top