Dzham

Untitled

Apr 15th, 2018
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.43 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <iterator>
  5. #include <unordered_map>
  6. #include <unordered_set>
  7. #include <string>
  8.  
  9. class Graph {
  10. private:
  11. int size_g;
  12. std::vector<std::vector<int>> data;
  13. std::vector<int> used;
  14.  
  15. public:
  16. std::vector<bool> isused;
  17. std::vector<int> colour;
  18. bool isisdouble = true;
  19. bool isiscycle = false;
  20. std::vector<int> cyclepath;
  21. std::unordered_map<int, int> parents;
  22. int max_path = 0;
  23.  
  24. Graph() {
  25. }
  26.  
  27. explicit Graph(int n) {
  28. data.resize(n);
  29. isused.resize(n);
  30. size_g = n;
  31. }
  32.  
  33. void insert(int a, int b) {
  34. if (a != b) {
  35. data[a - 1].push_back(b);
  36. data[b - 1].push_back(a);
  37. }
  38. }
  39.  
  40. void printgraph() {
  41. for (int i = 0; i < data.size(); i++) {
  42. for (auto j : data[i]) {
  43. std::cout << j << " ";
  44. }
  45. std::cout << '\n';
  46. }
  47. }
  48.  
  49. std::vector<int> dfs(int a) {
  50. std::vector<int> result;
  51. if (!isused[a - 1]) {
  52. isused[a - 1] = true;
  53. result.push_back(a);
  54. for (int i = 0; i < data[a - 1].size(); i++) {
  55. if (!isused[data[a - 1][i] - 1]) {
  56. std::vector<int> preres;
  57. preres = dfs(data[a - 1][i]);
  58. result.insert(result.end(), preres.begin(), preres.end());
  59. }
  60. }
  61. }
  62. return result;
  63. }
  64.  
  65. int sizetree(int a, int prev) {
  66. int max = -1;
  67. int second_max = -1;
  68. int b = 0;
  69. for (int i = 0; i < data[a - 1].size(); i++) {
  70. if (data[a - 1][i] != prev) {
  71. b = sizetree(data[a - 1][i], a) + 1;
  72. if (b >= max) {
  73. second_max = max;
  74. max = b;
  75. } else if (b < max && b > second_max) {
  76. second_max = b;
  77. }
  78. }
  79. }
  80. if (max + second_max + 2 > max_path) {
  81. max_path = max + second_max + 2;
  82. }
  83. return max;
  84. }
  85. };
  86.  
  87. int main() {
  88. int N, M;
  89. int a, b;
  90. std::cin >> N;
  91. if (N != 0) {
  92. Graph graph(N);
  93. for (int i = 0; i < N - 1; i++) {
  94. std::cin >> a >> b;
  95. graph.insert(a, b);
  96. }
  97. graph.sizetree(1, -1);
  98. std::cout << graph.max_path;
  99. }
  100. }
Add Comment
Please, Sign In to add comment