Problem hidden
NKPARITY - Mạng chẵn lẻ
Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkparity
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
Added by: | Jimmy |
Date: | 2008-01-14 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 |