Đếm số nút có đúng một nút con
Sau khi gốc hóa một cây, mỗi nút có một số nút con nhất định. Đếm xem có bao nhiêu nút
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
Sau khi gốc hóa một cây, mỗi nút có một số nút con nhất định. Đếm xem có bao nhiêu nút chỉ có đúng một nút con là bước kiểm tra nhanh để phát hiện cây bị "gãy": một cây mà nhiều nút có đúng một con thường là cây dạng dây, rất dễ tràn ngăn xếp khi duyệt đệ quy.
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ỳ.
Với mỗi nút, nút con là nút kề nằm xa gốc hơn một cạnh. Hãy đếm xem có bao nhiêu nút có đúng một nút con. Nút lá có 0 nút con nên không được tính, và nút không có nút con nào cũng không ảnh hưởng tới kết quả.
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: số nút có đúng một nút con.
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.
- 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
1
Ví dụ 2
Input
1
Output
0
Giải thích
Dữ liệu vào:
Gốc 1 có hai con 2, 3; nút 2 có một con 4; nút 3 và 4 không có con. Vậy chỉ nút 2 có đúng một con, kết quả in ra là 1.
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.
