DÂY CHUYỀN THƠNG BÁO CÁC HỌC SINH TRONG MỘT LỚP HỌC QUYẾT ĐỊN...

Bài 2 - Dây chuyền thơng báo Các học sinh trong một lớp học quyết định lập một dây chuyền thơng báo như sau. Mỗi học

sinh chọn một học sinh duy nhất khác làm người kế tiếp để truyền trực tiếp thơng báo. Khi mỗi học sinh nhận được thơng

báo, anh ta sẽ truyền ngay cho người kế tiếp của mình.

Dây chuyền thơng báo được gọi là tốt nếu nĩ thoả mãn điều kiện: Khi một học sinh A

bất kỳ gửi thơng báo cho

người kế tiếp A

, A

lại gửi cho người kế tiếp A

,..., cứ như vậy thì cuối cùng thơng báo sẽ đến mọi người trong lớp kể cả

người ban đầu (A

) đã phát ra thơng báo. Khơng nhất thiết mọi dây chuyền thơng báo là tốt.

Bài tốn đặt ra là: Cho trước một dây chuyền thơng báo, hãy tìm số ít nhất việc thay đổi người kế tiếp để cĩ thể nhận

được một dây chuyền thơng báo tốt.

Dữ liệu: file văn bản THONGBAO.INP trong đĩ dịng thứ nhất ghi số N < 10000 là số hcjc sinh trong lớp, các họcc

sinh này cĩ tên từ 1 đến N. Trong dịng tiếp theo ghi N số, số thứ i là tên người kế tiếp của học sinh i.

Kết quả: file THONGBAO.OUT như sau: dịng thứ nhất ghi số K là số thay đổi cần tiến hành (nếu dây chuyền thơng

báo đã cho là tốt thì K=0). Nếu K>0, trong K dịng tiếp theo, mỗi dịng ghi hai tên học sinh, người sau là người kế tiếp mới

được thay đổi của người trước.

Ví dụ:

THONGBAO.INP THONGBAO.OUT

10

3

6 9 2 7 3 1 10 3 6 9

1 4

10 8

8 5