fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <limits>
  4.  
  5.  
  6. class Tree {
  7.     struct Node {
  8.         int id;
  9.         std::vector<Node*> children;
  10.  
  11.         Node(int id) : id(id) {}
  12.     };
  13.  
  14.     public:
  15.         Tree(int id = 0) : mRoot(new Node(id)) {}
  16.  
  17.         inline Node* find(int id) const { return find_impl(mRoot, id); }
  18.         inline int getHeight() const { return getHeight_impl(mRoot); }
  19.  
  20.         inline void insert(int parent_id, int child_id) {
  21.             Node* parent = find(parent_id);
  22.             if (parent == nullptr) return;
  23.             parent->children.push_back(new Node(child_id));
  24.         }
  25.  
  26.     private:
  27.         Node* find_impl(Node* curr, int id) const {
  28.             if (curr == nullptr || curr->id == id) return curr;
  29.             for (const auto& child : curr->children) {
  30.                 auto it = find_impl(child, id);
  31.                 if (it != nullptr) return it;
  32.             }
  33.             return nullptr;
  34.         }
  35.  
  36.         int getHeight_impl(Node* curr) const {
  37.             if (curr == nullptr) return 0;
  38.  
  39.             int maxHeight = std::numeric_limits<int>::min();
  40.             for (const auto& child : curr->children) maxHeight = std::max(maxHeight, getHeight_impl(child));
  41.             return maxHeight + 1;
  42.         }
  43.  
  44.         Node* mRoot = nullptr;
  45. };
  46.  
  47. int main(void) {
  48.     std::ios_base::sync_with_stdio(false);
  49.     std::cin.tie(nullptr);
  50.  
  51.     int node_count;
  52.     std::cin >> node_count;
  53.  
  54.     Tree tree(0);
  55.     std::pair<int, int> tmp;
  56.  
  57.     for (int node_ind = 0; node_ind < node_count - 1; ++node_ind) {
  58.         std::cin >> tmp.first >> tmp.second;
  59.         tree.insert(tmp.first, tmp.second);
  60.     }
  61.  
  62.     std::cout << tree.getHeight() << std::endl;
  63.     return 0;
  64. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
5
0 1
0 2
1 3
3 4
stdout
copy 
-2147483644
https://ideone.com/wh0V3K
language:
C++ (gcc 8.3)
created:
30 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!