Advertisement
Guest User

Untitled

a guest
Jan 24th, 2020
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.18 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement