// Sử dụng cây để biểu diễn sơ đồ quản lý công ty

// Trong đội không có ai là quản lý của ai => Nhánh cây có độ sâu h phải cần ít nhất h đội

// Số đội cần thiết chính là độ sâu của cây (Nhánh có độ sâu lớn nhất)

​

using System;

using System.Collections.Generic;

​

public class Party

{

    public static int CountParties(int[] p)

    {

        // Tạo một mảng object employee

        var employees = new List<Employee>();

        for (int i = 0; i < p.Length; i++)

        {

            employees.Add(new Employee());

        }

        // Node tạm root

        // Sử dụng để làm parent cho những nhân viên k có ai quản lý => gốc của cây

        Employee root = new Employee();

        for (int i = 0; i < p.Length; i++)

        {

            if (p[i] == -1)

            {

                // Nếu nhân viên k có ai quản lý thì root sẽ quản lý

                // Add nhân viên i vào danh sách quản lý bởi root

                root.AddSubordinate(employees[i]);

                continue;

            }

            // Add nhân viên thứ i vào danh sách quản lý bởi p[i] - 1

            // Mảng employees đánh số từ 0 nên cần -1

            employees[p[i] - 1].AddSubordinate(employees[i]);

        }

        // Trả về độ sâu của cây

        // Trừ 1 để bỏ node root

        return root.GetHeight() - 1;

    }

    public static void Main(string[] args)

    {

        int[] p = [-1, 1, 1, 2, 3, -1];

        Console.WriteLine(CountParties(p));

        int[] p1 = [-1, 1];

        Console.WriteLine(CountParties(p1));

    }

}

​

// Class nhân viên

public class Employee

{

    public List<Employee> subordinates; // Nhân viên cấp dưới trực tiếp quản lý

    public Employee()

    {

        subordinates = new List<Employee>();

    }

    // Thêm một nhân viên cấp dưới trực tiếp quản lý

    public void AddSubordinate(Employee employee)

    {

        subordinates.Add(employee);

    }

    // Độ sâu của node hiện tại

    public int GetHeight()

    {       

        int max = 0; // Độ sâu lớn nhất của các node con

        foreach (var subordinate in subordinates)

        {

            int height = subordinate.GetHeight(); // Lấy độ sâu của các node con

            if (max < height)

                max = height;

        }

        return max + 1; // Độ sâu lớn nhất của các node con + node hiện tại

    }

}