Độ cao của cây có gốc
Cây có gốc là cấu trúc đầu tiên mà người mới học đồ thị cần nắm: có đúng một nút gốc,
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Cây có gốc là cấu trúc đầu tiên mà người mới học đồ thị cần nắm: có đúng một nút gốc, mọi nút khác có đúng một nút cha, và xuất phát từ gốc đi theo các cạnh cha - con thì chạm được tới mọi nút của cây. Câu hỏi mở đầu quen thuộc là: cây này "cao" bao nhiêu?
Yêu cầu
Cho một cây gồm n nút đánh số từ 1 đến n, dữ liệu là danh sách cạnh. Quy ước: nút 1 là gốc của cây. Mỗi cạnh được ghi bằng hai đầu mút và có thể ghi theo chiều bất kỳ (cha trước con hay con trước cha đều được).
Độ sâu của một nút là số cạnh trên đường đi từ gốc tới nút đó, vì vậy gốc có độ sâu 0. Độ cao của cây là độ sâu lớn nhất trong tất cả các nút. Hãy in ra độ cao của cây.
Quy ước nộp bài
Nộp chương trình solution.cpp đọc dữ liệu từ stdin và in kết quả ra stdout. Chỉ in đúng một số nguyên, không in thêm chữ nào khác.
Input
- Dòng đầu tiên: số nguyên n (1 <= n <= 10).
- n - 1 dòng tiếp theo: mỗi dòng hai số nguyên u v là một cạnh của cây.
- Khi n = 1 thì không có dòng cạnh nào.
Output
Một số nguyên duy nhất: độ cao của cây, tính theo số cạnh.
Ràng buộc
- Dữ liệu luôn là một cây hợp lệ: liên thông, đúng n - 1 cạnh, không có cạnh lặp.
- Thứ tự các dòng cạnh là tùy ý, cạnh có thể ghi con trước cha.
- Độ cao không vượt quá 5.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
4
1 2
1 3
2 4
Output
2
Ví dụ 2
Input
1
Output
0
Giải thích
Dữ liệu vào:
Cây có gốc 1; nút 1 có hai con là 2, 3; nút 2 có con 4. Độ sâu của bốn nút lần lượt là 0, 1, 1, 2, nên độ cao là 2. Kết quả in ra là 2.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
