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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
//#include <gtest/gtest.h>
using std::vector;
using std::queue;
class Node;
class Node {
public:
int key;
Node *parent;
vector<Node *> children;
Node() {
this->parent = NULL;
}
void setParent(Node *theParent) {
parent = theParent;
parent->children.push_back(this);
}
};
int treeLevelCounter(vector<Node> &nodes, int rootIndex) {
int levelCounter = 1;
queue<Node *> q;
int popCount = 0;
int childrenCount = nodes[rootIndex].children.size();
int grandChildrenCount = 0;
for (int i = 0; i < childrenCount; i++) {
q.push(nodes[rootIndex].children[i]);
}
while (!q.empty()) {
if (popCount < childrenCount) {
Node *n = q.front();
q.pop();
int i = n->children.size();
if (i != 0) {
for (int j = 0; j < i; j++) {
q.push(n->children[j]);
}
}
grandChildrenCount = grandChildrenCount + i;
popCount = popCount + 1;
} else {
popCount = 0;
childrenCount = grandChildrenCount;
grandChildrenCount = 0;
levelCounter = levelCounter + 1;
}
}
return levelCounter + 1;
}
int getHeight(vector<int> &a) {
vector<Node> nodes;
nodes.resize(a.size());
int rootIndex = 0;
for (size_t i = 0; i < a.size(); i++) {
int parentIndex = a[i];
if (parentIndex == -1) {
rootIndex = i;
} else {
nodes[i].setParent(&nodes[parentIndex]);
}
}
return treeLevelCounter(nodes, rootIndex);
}
//TEST(GetTreeHeight, t1) {
// vector<int> a = {4, -1, 4, 1, 1};
// ASSERT_EQ(3, getHeight(a));
//}
//
//TEST(GetTreeHeight, t2) {
// vector<int> a = {-1, 0, 4, 0, 3};
// ASSERT_EQ(4, getHeight(a));
//}
//
//TEST(GetTreeHeight, t3) {
// vector<int> a = {9, 7, 5, 5, 2, 9, 9, 9, 2, -1};
// ASSERT_EQ(4, getHeight(a));
//}
//
//TEST(GetTreeHeight, t4) {
// vector<int> a = {8, 8, 5, 6, 7, 3, 1, 6, -1, 5};
// ASSERT_EQ(6, getHeight(a));
//}
int main() {
size_t an;
std::cin >> an;
vector<int> a(an);
for (size_t i = 0; i < an; i++) {
std::cin >> a[i];
}
std::cout << getHeight(a) << std::endl;
}
|
