Advertisement
Guest User

Untitled

a guest
Jun 27th, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. vector <int> V[1000001];
  7. int najdalszy=0;
  8. int kolor[1000001];
  9. int odl=0;
  10. int index=0;
  11.  
  12. void DFS1(int a)
  13. {
  14. kolor[a]=1;
  15. for (int i=0;i<V[a].size();i++)
  16. {
  17. if (kolor[V[a][i]]==0)
  18. {
  19. odl++;
  20. if (najdalszy<odl)
  21. {
  22. index=V[a][i];
  23. najdalszy=odl;
  24. }
  25. DFS1(V[a][i]);
  26. odl--;
  27. }
  28. }
  29. }
  30. void DFS2(int n)
  31. {
  32. kolor[n]=2;
  33. for (int i=0;i<V[n].size();i++)
  34. {
  35. if (kolor[V[n][i]]==1)
  36. {
  37. odl++;
  38. najdalszy = max (odl, najdalszy);
  39. DFS2(V[n][i]);
  40. odl--;
  41. }
  42. }
  43. }
  44. int main()
  45. {
  46. std::ios_base::sync_with_stdio(false);
  47. int n;
  48. cin >> n;
  49. for (int i=1;i<n;i++)
  50. {
  51. int a, b;
  52. cin >> a >> b;
  53. V[a].push_back(b);
  54. V[b].push_back(a);
  55. }
  56. DFS1(1);
  57. odl=0;
  58. najdalszy=0;
  59. DFS2(index);
  60. cout << najdalszy;
  61. return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement