Guest User

Untitled

a guest
Jul 22nd, 2018
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const int N = 40001;
  7.  
  8. vector<int> G[N];
  9. vector<int> upatrono;
  10. int used[N];
  11. int intime[N];
  12. int outtime[N];
  13. int time = 0;
  14.  
  15. void dfs( int v );
  16.  
  17. int main()
  18. {
  19.     int n,k,p,m;
  20.     //freopen("input.txt","r",stdin);
  21.     //freopen("output.txt","w",stdout);
  22.     cin>>n;
  23.     for( int i = 0; i<n; i++ )
  24.     {
  25.         cin>>k>>p;
  26.         if( p==-1 )
  27.             upatrono.push_back(k);
  28.         G[p].push_back(k);
  29.     }
  30.  
  31.     dfs( upatrono[0] );
  32.  
  33.     cin>>m;
  34.     for( int j=0; j<m; j++ )
  35.     {
  36.         cin>>k>>p;
  37.         if( intime[k] < intime[p] && outtime[k] > outtime[p] )
  38.             cout<<1<<endl;
  39.         else if( intime[p] < intime[k] && outtime[p] > outtime[k] )
  40.             cout<<2<<endl;
  41.         else cout<<0<<endl;
  42.     }
  43.     return 0;
  44. }
  45. void dfs( int v )
  46. {
  47.     used[v] = true;
  48.     intime[v] = time++;
  49.     for(int i = 0; i<G[v].size(); i++ )
  50.     {
  51.         int adj = G[v][i];
  52.         if( !used[adj] )
  53.         dfs( G[v][i] );
  54.     }
  55.     outtime[v] = time++;
  56. }
Add Comment
Please, Sign In to add comment