Advertisement
AdelKhalilov

Untitled

Jul 8th, 2017
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.15 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int n;
  7. vector <int> g[100010];
  8. int in[100010];
  9. int out[100010];
  10. int t = 1 ;
  11. int color[100010];
  12. int q = 0;
  13.  
  14. void dfs (int v)
  15. {
  16. in[v] = t;
  17. t++;
  18. color[v] = 1;
  19. for (int i = 0; i < g[v].size(); i++)
  20. {
  21. int u = g[v][i];
  22. if (color[u] == 0)
  23. {
  24. dfs(u);
  25. }
  26. }
  27. out[v] = t;
  28. t++;
  29. color[v] = 2;
  30. }
  31.  
  32. int main()
  33. {
  34. cin >> n;
  35. for (int i = 0; i < n; i++)
  36. {
  37. int x;
  38. cin >> x;
  39. if (x != 0)
  40. {
  41. g[i].push_back(x - 1);
  42. g[x - 1].push_back(i);
  43. }
  44. else
  45. {
  46. q = i;
  47. }
  48. }
  49.  
  50.  
  51. for (int i = 0 ; i < sizeof(color) ; i++)
  52. color[i] = 0;
  53.  
  54. dfs(q);
  55.  
  56. int m;
  57. cin >> m;
  58.  
  59. for (int i = 0; i < m; i++)
  60. {
  61. int a, b;
  62. cin >> a >> b;
  63. if (in[a - 1] < in[b - 1] && out[b - 1] < out [a - 1])
  64. {
  65. cout << "1" << endl;
  66. }
  67. else
  68. {
  69. cout << "0" << endl;
  70. }
  71. }
  72. return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement