NKPARITY - Mạng chẵn lẻ
Giới hạn- Thời gian: 0.13s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Có N máy tính đánh số từ 1 đến N được nối với nhau thành một mạng bởi các đoạn nối trực tiếp giữa một số cặp máy nào đó (gọi là kênh). Mạng được gọi là chẵn lẻ nếu như trong nó tìm được hai máy có thể trao đổi thông tin với nhau thông qua một số chẵn kênh cũng như thông qua một số lẻ kênh.
Yêu cầu: Kiểm tra xem mạng đã cho có phải chẵn lẻ hay không? Nếu câu trả lời là phủ định hãy tìm tập con X các máy có lực lượng lớn nhất thoả mãn điều kiện: đối với hai máy bất kỳ trong X nếu chúng có thể trao đổi thông tin với nhau thì bao giờ cũng phải thông qua một số chẵn kênh.
Dữ liệu
- Dòng đầu tiên chứa số N (N<=300).
- Mỗi dòng trong số các dòng tiếp theo chứa một cặp số i, j cho biết máy i được nối trực tiếp với máy j.
Kết quả
-
Nếu mạng là
chẵn lẻ
thì ghi vào dòng đầu tiên thông báo 'YES', ngược lại ghi 'NO' sau đó ghi kết quả theo qui cách sau:
- Dòng thứ hai ghi số phần tử của tập X.
- Trong các dòng tiếp theo ghi các chỉ số của các máy trong tập X theo thứ tự tăng dần, các chỉ số được ghi cách nhau bởi ít nhất một dấu cách.
Ví dụ
Dữ liệu: 5 1 2 2 3 3 4 4 5 5 1 Kết qủa YES Dữ liệu 3 1 2 Kết quả NO 2 2 3
- Người up: paulmcvn