02-data_structures/01-basic_data_structures/02-tree_height/tree-height.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <iostream>
#include <vector>
#include <algorithm>

class TreeHeight {
  int n;
  int root;
  std::vector<int> parent;

public:
  void read() {
      std::cin >> n;
      parent.resize(n);
      for (int i = 0; i < n; i++) {
          std::cin >> parent[i];
          if (parent[i] < 0)
              root = i;
      }
      /* std::cout << root << std::endl; */
  }

  int compute_height()
  {
      std::vector<int> heights(n);
      for (int vertex = 0; vertex < n; vertex++) {
          if (heights[vertex] != 0)
              continue;
          int height = 0;
          for (int i = vertex; i != -1; i = parent[i]) {
              height++;
              if (height > heights[i])
                  heights[i] = height;
              else break;
          }
      }
      return heights[root];
  }

};

int main() {
  std::ios_base::sync_with_stdio(0);
  TreeHeight tree;
  tree.read();
  std::cout << tree.compute_height() << std::endl;
}