Chú bò hư hỏng

Xem dạng PDF

Gửi bài giải

Điểm: 100,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, Python
Chú bò hư hỏng
Mô tả và yêu cầu

Chú bò hư hỏng.
Nông dân John có N (1≤ N ≤ 250) con bò đánh số từ 1..N chơi trên bãi cỏ. Để tránh bị lạc
mất các con bò, mỗi con bò có thể được nối với một số con bò khác bằng dây thừng. Có
tất cả M (1 ≤ M ≤ N*(N-1)/2) dây thừng nối các con bò. Tất nhiên, không có 2 con bò mà
có nhiều hơn 1 dây thừng nối giữa chúng. Dữ liệu cho biết mỗi cặp con bò c1 và c2 là nối
với nhau (1 ≤ c1 ≤ N; 1 ≤ c2 ≤ N; c1 ≠ c2). Nông dân John buộc cố định con bò 1 bằng sợi
dây xích. Các con bò khác phải nối với con bò 1 bằng một số sợi dây thừng. Tuy nhiên,
một số con bò hư hỏng không như vậy. Hãy giúp nông dân John tìm các con bò hư hỏng
đó (không kết nối tới bò 1). Dĩ nhiên, con bò thứ 1 luôn nối tới chính nó.
Dữ liệu: từ file văn bản CHUBO.INP gồm:
 Dòng đầu tiên: 2 số nguyên cách nhau bởi dấu cách: N và M.
 Mỗi dòng thứ i trong M dòng tiếp theo, cho biết 2 con bò c1 và c2 nối với nhau bằng
sợi dây thứ i (c1 và c2 cách nhau bởi dấu cách).
Kết quả: ghi ra file văn bản CHUBO.OUT chứa số 0 nếu không có con bò hư hỏng. Ngược
lại, ghi ra trên mỗi dòng một số nguyên là thứ tự con bò hư hỏng theo thứ tự tăng dần.

Ví dụ
CHUBO.INP               CHUBO.OUT                    GIẢI THÍCH
               6 4                      4                       Dễ thấy, các con bò 4,
               1 3                      5                       5, và 6 không nối tới
               2 3                      6                       con bò 1.
               1 2
               4 5                                              1---2  4---5
                                                                  \  |
                                                                   \ |      6
                                                                    \|
                                                                     3

Tải PDF gốc


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.