Đếm số nút theo từng độ sâu
Duyệt cây theo tầng (BFS) chia các nút thành từng lớp: gốc một mình một lớp, các con của
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
Duyệt cây theo tầng (BFS) chia các nút thành từng lớp: gốc một mình một lớp, các con của gốc là lớp kế tiếp, và cứ thế. Bảng "mỗi lớp có bao nhiêu nút" vừa kiểm tra được hàm duyệt theo tầng có đúng không, vừa cho biết cây cân hay lệch.
Yêu cầu
Cho một cây gồm n nút đánh số từ 1 đến n và n - 1 cạnh. Quy ước: nút 1 là gốc của cây, mỗi cạnh có thể được ghi theo chiều bất kỳ. Độ sâu của gốc là 0, và độ sâu của mỗi nút khác là số cạnh trên đường đi từ gốc tới nút đó.
Hãy in ra, với mỗi độ sâu từ 0 đến độ sâu lớn nhất, một dòng dạng d:c trong đó d là độ sâu và c là số nút có độ sâu đó. Các dòng phải theo thứ tự d tăng dần và mọi độ sâu từ 0 đến độ sâu lớn nhất đều phải được in, kể cả những độ sâu chỉ có một nút.
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. Mỗi dòng đúng dạng d:c, 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
Nhiều dòng, mỗi dòng dạng d:c, in từ độ sâu 0 tới độ sâu lớn nhất.
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.
- Số dòng phải bằng độ sâu lớn nhất cộng một.
- 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
0:1
1:2
2:1
Ví dụ 2
Input
1
Output
0:1
Giải thích
Dữ liệu vào:
Độ sâu của các nút: nút 1 là 0; nút 2, 3 là 1; nút 4 là 2. Vậy kết quả là:
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.
