Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- const int N = 40001;
- vector<int> G[N];
- vector<int> upatrono;
- int used[N];
- int intime[N];
- int outtime[N];
- int time = 0;
- void dfs( int v );
- int main()
- {
- int n,k,p,m;
- //freopen("input.txt","r",stdin);
- //freopen("output.txt","w",stdout);
- cin>>n;
- for( int i = 0; i<n; i++ )
- {
- cin>>k>>p;
- if( p==-1 )
- upatrono.push_back(k);
- G[p].push_back(k);
- }
- dfs( upatrono[0] );
- cin>>m;
- for( int j=0; j<m; j++ )
- {
- cin>>k>>p;
- if( intime[k] < intime[p] && outtime[k] > outtime[p] )
- cout<<1<<endl;
- else if( intime[p] < intime[k] && outtime[p] > outtime[k] )
- cout<<2<<endl;
- else cout<<0<<endl;
- }
- return 0;
- }
- void dfs( int v )
- {
- used[v] = true;
- intime[v] = time++;
- for(int i = 0; i<G[v].size(); i++ )
- {
- int adj = G[v][i];
- if( !used[adj] )
- dfs( G[v][i] );
- }
- outtime[v] = time++;
- }
Add Comment
Please, Sign In to add comment