Advertisement
Guest User

Untitled

a guest
Sep 19th, 2017
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.62 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4. #if defined(__unix__) || defined(__APPLE__)
  5. #endif
  6.  
  7. class Node;
  8.  
  9. class Node {
  10. public:
  11. int key;
  12. Node *parent;
  13. std::vector<Node *> children;
  14.  
  15. Node() {
  16. this->parent = NULL;
  17. }
  18.  
  19. void setParent(Node *theParent) {
  20. parent = theParent;
  21. parent->children.push_back(this);
  22. }
  23.  
  24. int height(Node node)
  25. {
  26. if (node.children.size() == 0)
  27. return 0;
  28.  
  29. int maxH = 0;
  30. for (int i = 0; i < node.children.size(); ++i)
  31. {
  32. if (maxH < height(*node.children[i]))
  33. {
  34. maxH = height(*node.children[i]);
  35. }
  36. }
  37. maxH += 1;
  38. return maxH;
  39. }
  40. };
  41.  
  42.  
  43. int main()
  44. {
  45. std::ios_base::sync_with_stdio(0);
  46. int n;
  47. std::cin >> n;
  48. int root;
  49.  
  50. std::vector<Node> nodes;
  51. nodes.resize(n);
  52. for (int child_index = 0; child_index < n; child_index++) {
  53. int parent_index;
  54. std::cin >> parent_index;
  55. if (parent_index >= 0)
  56. nodes[child_index].setParent(&nodes[parent_index]);
  57. else
  58. {
  59. //нужно отловить корень
  60. root = child_index;
  61. }
  62. nodes[child_index].key = child_index;
  63. }
  64. std::cout << nodes[root].height(nodes[root]) + 1 << std::endl;
  65. //for (int i =0; i < n; ++i)
  66. //{
  67. // for (int j = 0; j < nodes[i].children.size(); ++j)
  68. // {
  69. // std::cout << nodes[i].children[j];
  70. // }
  71. // std::cout << std::endl;
  72. //}
  73. return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement