Bài tập Lập trình - Bài 1: Nén cây

Bài tập lập trình 1: Nén cây

Mỗi cây gán nhãn với n đỉnh có thể biểu diễn duy nhất bởi Prufer code của nó. Do kích thước

ngắn của Prufer code, ta xem nó như một biểu diễn nén của cây. Bạn hãy viết chương trình nhập

vào một cây gán nhãn và in ra màn hình Prufer code của nó.

Cụ thể, bạn phải cài đặt chương trình làm việc sau.

• Input (nhập từ bàn phím): Cây gán nhãn {0, ..., n − 1} với số đỉnh n < 100000. Cây này

được biểu diễn bởi danh sách cạnh.

• Output (ra màn hình): Mã Prufer code của cây này.

Ví dụ: Với dữ liệu vào:

0 2

0 3

2 4

2 6

2 9

6 1

6 5

9 7

9 8

Dòng đầu tiên thể hiện số cạnh của cây; mỗi dòng tiếp theo thể hiện một cạnh của cây.

Với dữ liệu này, chương trình nên output ra mã Prufer:

6 0 2 6 2 9 9 2

Test chương trình: Để test chương trình của mình, bạn có thể sử dụng mã nguồn sinh cây gán

nhãn ngẫu nhiên từ mã Prufer (trong thư mục PruferCodes); và sử dụng cây này như Input của

chương trình để tìm lại mã Prufer.

Chú ý:

• Bạn chỉ submit file source code lên hệ thống

• Hệ thống sẽ tự kiểm tra việc sao chép bài. Mọi bài sao chép (dù chỉ 1 phần) sẽ bị điểm 0

và bị cảnh cáo.

1 trang Thùy Anh 26/04/2022 23120

Download

Bạn đang xem tài liệu "Bài tập Lập trình - Bài 1: Nén cây", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm: