【題解】Codeforces 115A. Party

【題目敘述】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)
分享本文 Share with friends