Advertisement
Guest User

Untitled

a guest
Sep 20th, 2017
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.76 KB | None | 0 0
  1. #include <cstdio>
  2. #include <vector>
  3. #include <queue>
  4. #include <iostream>
  5. using namespace std;
  6. vector <long long int> b, d;
  7. long long int N;
  8. queue <long long int> q;
  9. vector<long long int> G[100000];
  10. void addEdge(long long int a, long long int b)
  11. {
  12. G[a].push_back(b);
  13. G[b].push_back(a);
  14. }
  15. int main()
  16. {
  17.  
  18. cin >> N;
  19. long long int p;
  20. for (int i = 0; i < N; i++)
  21. {
  22. cin >> p;
  23. addEdge(i + 1, p);
  24. b.push_back(0);
  25. d.push_back(0);
  26. }
  27.  
  28. long long int t = 0;
  29. q.push(0);
  30. while (!q.empty())
  31. {
  32.  
  33. long long int u = q.front();
  34. q.pop();
  35.  
  36. for(long long int i = 0; i < G[u].size(); ++i)
  37. {
  38. long long int v =G[u][i];
  39. if (b[v] == 0)
  40. {
  41. b[v] = 1;
  42. b[u] = 1;
  43. d[v] = d[u] + 1;
  44. q.push(v);
  45. if ( v == N) t = 1;
  46. }
  47.  
  48. }
  49.  
  50. }
  51.  
  52.  
  53.  
  54.  
  55. long long int m = 0, m1 = 0;
  56. if (t == 0) N = N - 1;
  57. for (long long int u = 0; u <= N; u++)
  58. if (d[u] > m)
  59. {
  60. m = d[u];
  61. m1 = u;
  62.  
  63. }
  64.  
  65.  
  66. cout << m1;
  67. return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement