Liệt kê các nút lá theo thứ tự tăng dần
Khi cây được gốc hóa, "lá" là những nút không còn nút con nào. Muốn kiểm tra một thuậ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
Khi cây được gốc hóa, "lá" là những nút không còn nút con nào. Muốn kiểm tra một thuật toán duyệt cây có đi tới hết các nhánh hay không, bước đầu tiên thường là in danh sách lá ra để đối chiếu.
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, và mỗi cạnh có thể được ghi theo chiều bất kỳ.
Một nút được gọi là lá nếu nó không có nút con nào. Với mỗi nút khác gốc, điều này tương đương "bậc của nút bằng 1". Gốc không bao giờ được tính là lá, kể cả khi cây chỉ có duy nhất nút gốc.
Hãy in nhãn của tất cả các lá theo thứ tự tăng dần, cách nhau bởi đúng một dấu cách trên một dòng. Nếu cây không có lá nào, in ra -1.
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 dòng, 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 dòng chứa nhãn các lá theo thứ tự tăng dần, cách nhau một dấu cách; hoặc -1 nếu cây không có lá.
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.
- Nhãn các lá phải theo thứ tự tăng dần, không theo thứ tự duyệ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
3 4
Ví dụ 2
Input
5
1 2
2 3
1 4
4 5
Output
3 5
Giải thích
Dữ liệu vào:
Gốc 1 có hai con 2, 3; nút 2 có con 4. Hai nút 3 và 4 không có con nào nên là lá. Kết quả in ra: 3 4.
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.
