【題目敘述】http://codeforces.com/problemset/problem/115/A
【解題想法】樹的高度
#include <iostream>
#include <vector>
using namespace std;
int n, p[2005], d[2005], ans;
vector <int> v[2005], root;
void dfs(int x, int dep){
d[x] = dep;
ans = max(ans, dep);
for (auto i:v[x]){
dfs(i, dep+1);
}
return;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++){
cin >> p[i];
if (p[i] != -1) v[p[i]].push_back(i);
else root.push_back(i);
}
for (auto i:root){
dfs(i, 1);
}
cout << ans << "\n";
}
Python code (credit: Amy Chou)
import sys
sys.setrecursionlimit(1000000)
def dfs(x):
if len(child[x]) == 0:
H[x] = 1
else:
mx = 0
for y in child[x]:
dfs(y)
mx = max(mx, H[y] + 1)
H[x] = mx
n= int(input())
child = [[] for _ in range(n)]
pa = [-1 for _ in range(n)]
root = []
for i in range(n):
x = int(input())
if x == -1:
root.append(i)
continue
pa[i] = x - 1 #zero-based
child[x-1].append(i)
H = [0 for _ in range(n)]
group = 0
for r in root:
dfs(r)
group = max(group, H[r])
print(group)