Bài tập Lập trình về đồ thị - 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: 9 0 2 0 3 2 4 2 6 2 9 6 1 6 5 9 7 9 8 4 5 61 7 8 9 3 0 2 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