Guest User

Untitled

a guest
Jun 27th, 2015
1,961
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.15 KB | None | 0 0
  1. #include "stdio.h"
  2. #include "stdlib.h"
  3. #include "math.h"
  4. #include "string.h"
  5. #include "stdint.h"
  6. #include "vector"
  7. #include "set"
  8. #include "stack"
  9. #include "queue"
  10. #include "map"
  11. #include "algorithm"
  12. #define min(a,b) (a)<(b)?(a):(b)
  13. #define max(a,b) (a)>(b)?(a):(b)
  14. #define abso(a) (a)>(0)?(a):(-a)
  15. #define VI vector<int>
  16. #define pb push_back
  17. #define all(c) c.begin(), c.end()
  18. #define lli long long int
  19. using namespace std;
  20.  
  21. int inline inp()
  22. {
  23. int n=0;
  24. char c=getchar_unlocked();
  25. while(c < '0' || c >'9') {c=getchar_unlocked();}
  26. while(c>='0' && c<='9')
  27. {
  28. n=(n<<3)+(n<<1)+c-'0';
  29. c=getchar_unlocked();
  30. }
  31. return n;
  32. }
  33.  
  34. vector< vector< int > > graph;
  35. bool visited[10010];
  36. int length[10010], len, idx;
  37.  
  38.  
  39. void BFS(int src)
  40. {
  41. memset(visited,false, sizeof(visited));
  42. visited[src] = true;
  43. len = 0;
  44. length[src] = len;
  45.  
  46. queue<int> Q;
  47. Q.push(src);
  48.  
  49. while(!Q.empty())
  50. {
  51. int cur = Q.front();
  52. Q.pop();
  53.  
  54. for (VI::iterator it = graph[cur].begin(); it != graph[cur].end(); ++it)
  55. {
  56. if(!visited[*it])
  57. {
  58. visited[*it] = true;
  59. Q.push(*it);
  60. length[*it] = length[cur]+1;
  61. }
  62. }
  63. }
  64.  
  65. }
  66. int main()
  67. {
  68. int n = inp();
  69. graph = vector< VI > (n);
  70. int p,q, flag = 0;
  71. for (int i = 0; i < n-1; ++i)
  72. {
  73. p = inp();
  74. q = inp();
  75. p--;
  76. q--;
  77. graph[p].pb(q);
  78. graph[q].pb(p);
  79. }
  80.  
  81.  
  82. //checking for connected components
  83.  
  84. BFS(0);
  85.  
  86. int maxi = 0,idx;
  87.  
  88. for (int i = 0; i < n; ++i)
  89. {
  90. if(length[i] > maxi)
  91. {
  92. maxi = length[i];
  93. idx = i;
  94. }
  95. // printf("%d ",length[i] );
  96. }
  97. //printf("\n");
  98.  
  99.  
  100. //printf("doing bfs for %d\n",idx );
  101. BFS(idx);
  102.  
  103. maxi = 0;
  104. for (int i = 0; i < n; ++i)
  105. {
  106. if(length[i] > maxi)
  107. {
  108. maxi = length[i];
  109. idx = i;
  110. }
  111. // printf("%d ",length[i] );
  112. }
  113. //printf("\n");
  114. printf("%d\n",maxi );
  115.  
  116. return 0;
  117. }
Advertisement
Add Comment
Please, Sign In to add comment