fork download
copy 
  1. /**
  2.  * created by : Mostafa Wael (Phoenix)
  3.  * problem name : Valid BFS 
  4.  */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. void make_edge(int &u, int &v, vector<vector<int>>&tree)
  9. {
  10.     tree[u].push_back(v);
  11.     tree[v].push_back(u);
  12. }
  13.  
  14. bool check_path_isCorrect(int source, int &n, vector<vector<int>> &tree, vector<bool> &isVisited, queue<int> &path)
  15. {
  16.     if(source!=path.front()) 
  17.         return false;
  18.     path.pop();
  19.     queue<int> q;
  20.     q.push(source);
  21.     isVisited[source]=true;
  22.     while (!q.empty()){
  23.         int u=q.front(); q.pop();
  24.         int sz=tree[u].size()+(u==source); // first node has no parent 
  25.         while(--sz){
  26.             isVisited[path.front()]=true;
  27.             q.push(path.front());
  28.             path.pop();
  29.         }
  30.         for(auto v:tree[u])
  31.             if(!isVisited[v])
  32.                 return false;
  33.     }
  34.     return true;
  35. }
  36.  
  37. int main()
  38. {
  39.     ios::sync_with_stdio(0);
  40.     cin.tie(0);
  41.     cout.tie(0);
  42.     /**
  43.      * we can use path to mark node and then check for neighbors node if visited or no 
  44.      */
  45.     int n;
  46.     cin >> n;
  47.     vector<vector<int>> tree(n);
  48.     for (int i = 1; i < n; i++)
  49.     {
  50.         int u, v;
  51.         cin >> u >> v;
  52.         make_edge(--u, --v, tree);
  53.     }
  54.     queue<int> path;
  55.     for(int i=0,u;i<n;i++){
  56.         cin>>u;
  57.         path.push(--u);
  58.     }
  59.     vector<bool> isVisited(n);
  60.     cout << (check_path_isCorrect(0, n, tree, isVisited, path) ? "Yes" : "No");
  61.     return 0;
  62. }
  63.  
Runtime error #stdin #stdout 0s 5548KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/J3oqCk
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!