Đề thi chọn học sinh giỏi Lớp 12 cấp tỉnh môn Tin học - Sở GD&ĐT Đồng Tháp (Có đáp án)

(Bản scan)

Bài 3. (6,0 điểm) ĐỒNG CỎ
Trên cánh đồng cỏ hiện có n con bò đang ăn cỏ, các con bò được đánh số từ 1 đến n, trong
đó con bò đầu đàn được đánh số 1. Những con bò luôn đi vòng quanh để tìm những bãi cỏ ngon
nhất. Vì lo sợ những con bò sẽ đi vào những vườn rau bên cạnh nên người chăn bò đã dùng một
sô đoạn đây thừng cột các con bò với nhau, mỗi đoạn dây sẽ cột hai con bò nào đó lại, tật nhiên là
giữa hai con bò chỉ cần dùng tối đa một đoạn dây để cột. Tuy nhiên, lũ bò cũng rất tỉnh ranh,
những con được cột chung với nhau giờ đây lại cùng đi chung, nhật là con đầu đàn hay lôi kéo
những con khác đi chung. 'Thế là người chăn bò lại cột hắn con bò đầu đàn vào gốc cây trên đông
cỏ - khỏi đi đâu nữa hết!
Yêu cầu: Ilãy cho biết số lượng các con bò có khả năng đi vào những vườn rau bên cạnh.
Đó là những con bò nào?
Dữ liệu vào: Cho từ tệp văn bản DONGCO.INP có dạng:
-_ Dòng thứ nhất ghi hai số nguyên n, m tương ứng là số con bò và số đoạn dây thừng
dùng để cột hai con bò lại với nhau (1 < n < 30000, 0 < m < 100000)
- m đồng tiếp theo, mỗi dòng ghi hai số u, v cho biết đoạn dây thừng cột hai con bò thứ
u và thứ v lại với nhau (l1 < u, v Các sô trên cùng một dòng ghỉ cách nhau một dâu cách.