题解 | #上司的舞会#

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

using namespace std;

vector<int> adj[100005];

int dfs(int u) {
    if (adj[u].empty()) {
        return 1;
    }
    int max_child_depth = 0;
    for (int v : adj[u]) {
        max_child_depth = max(max_child_depth, dfs(v));
    }
    return 1 + max_child_depth;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> roots;
    for (int i = 1; i <= n; ++i) {
        int parent;
        cin >> parent;
        if (parent == -1) {
            roots.push_back(i);
        } else {
            adj[parent].push_back(i);
        }
    }

    int max_depth = 0;
    for (int root : roots) {
        max_depth = max(max_depth, dfs(root));
    }

    cout << max_depth << endl;

    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<Integer>[] adj;

    public static int dfs(int u) {
        if (adj[u].isEmpty()) {
            return 1;
        }
        int maxChildDepth = 0;
        for (int v : adj[u]) {
            maxChildDepth = Math.max(maxChildDepth, dfs(v));
        }
        return 1 + maxChildDepth;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }

        List<Integer> roots = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            int parent = sc.nextInt();
            if (parent == -1) {
                roots.add(i);
            } else {
                adj[parent].add(i);
            }
        }

        int maxDepth = 0;
        for (int root : roots) {
            maxDepth = Math.max(maxDepth, dfs(root));
        }

        System.out.println(maxDepth);
    }
}

import sys

# 增加递归深度限制
sys.setrecursionlimit(100005)

def solve():
    n_str = sys.stdin.readline()
    if not n_str: return
    n = int(n_str)
    
    parents = list(map(int, sys.stdin.readline().split()))
    
    adj = [[] for _ in range(n + 1)]
    roots = []
    
    for i, p in enumerate(parents):
        employee_id = i + 1
        if p == -1:
            roots.append(employee_id)
        else:
            adj[p].append(employee_id)

    memo = {}
    def dfs(u):
        if u in memo:
            return memo[u]
        if not adj[u]:
            return 1
        
        max_child_depth = 0
        for v in adj[u]:
            max_child_depth = max(max_child_depth, dfs(v))
        
        memo[u] = 1 + max_child_depth
        return memo[u]

    max_depth = 0
    for root in roots:
        max_depth = max(max_depth, dfs(root))
        
    print(max_depth)

solve()