Guest User

Untitled

a guest
Jul 16th, 2018
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.86 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:16777216")
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <vector>
  5. #include <map>
  6. using namespace std;
  7. const int MAXN = 40002;
  8.  
  9. vector <int > G[MAXN];
  10. int i, j, k, n, dd, idv, idu, t, q, r;
  11. int in[MAXN], out[MAXN], v, u;
  12.  
  13. void dfs(int v, int p)
  14. {
  15.     in[v] = ++t;
  16.     int u;
  17.     for (int i = 0; i < G[v].size(); i++)
  18.     {
  19.         u = G[v][i];
  20.         if (!in[u] && p !=u)
  21.             dfs(u, v);
  22.     }
  23.     out[v] = ++t;
  24. }
  25.  
  26. int main()
  27. {
  28.     //freopen("input.txt","r",stdin);
  29.     scanf("%d", &n);
  30.    
  31.  
  32.     for (i = 0; i < n; i++)
  33.     {
  34.         scanf("%d%d", &v, &u);
  35.         if (u == -1)
  36.             r = v;
  37.         else
  38.             G[u].push_back(v);
  39.     }
  40.     cin >> q;
  41.     dfs(r, 0);
  42.     while (q --)
  43.     {
  44.         scanf("%d%d", &v, &u);
  45.         if (in[v] < in[u] && out[v] > out[u])
  46.             printf("1\n");
  47.         else
  48.             if (in[v] > in[u] && out[v] < out[u])
  49.                 printf("2\n");
  50.             else
  51.                 printf("0\n");
  52.     }
  53. return 0;
  54. }
Add Comment
Please, Sign In to add comment