VOI 06 Bài 5 - Mạng máy tính
View as PDFMột hệ thống ~n~ máy tính (các máy tính được đánh số từ ~1~ đến ~n)~ được nối lại thành một mạng bởi ~m~ kênh nối, mỗi kênh nối hai máy nào đó và cho phép ta truyền tin một chiều từ máy này đến máy kia. Giả sử ~s~ và ~t~ là ~2~ máy tính trong mạng. Ta gọi đường truyền từ máy ~s~ đến máy ~t~ là một dãy các máy tính và các kênh nối chúng có dạng:
~s = u_{1}~, ~e_{1}~, ~u_{2}~, ..., ~u_{i}~, ~e_{i}~, ~u_{i + 1}~, ..., ~u_{k - 1}~, ~e_{k - 1}~, ~u_{k} = t~
trong đó ~u_{1}~, ~u_{2}~, ..., ~u_{k}~ là các máy tính trong mạng, ~e_{i} -~ kênh truyền tin từ máy ~u_{i}~ đến máy ~u_{i + 1}~. ~(i = 1~, ~2~, ..., ~k - 1)~.
Mạng máy tính được gọi là thông suốt nếu như đối với hai máy ~u~, ~v~ bất kỳ ta luôn có đường truyền tin từ ~u~ đến ~v~ và đường truyền tin từ ~v~ đến ~u~. Mạng máy tính được gọi là hầu như thông suốt nếu đối với hai máy ~u~, ~v~ bất kỳ, hoặc là có đường truyền từ ~u~ đến ~v~, hoặc là có đường truyền từ ~v~ đến ~u~.
Biết rằng mạng máy tính đã cho là hầu như thông suốt nhưng không thông suốt.
Yêu cầu: hãy xác định xem có thể bổ sung đúng một kênh truyền tin để biến mạng đã cho trở thành thông suốt được không?
Input
- Dòng đầu tiên ghi ~2~ số nguyên ~n~ và ~m~.
- Dòng thứ ~i~ trong số ~m~ dòng tiếp theo mô tả kênh nối thứ ~i~ bao gồm ~2~ số nguyên dương ~u_{i}~ và ~v_{i}~ cho biết kênh nối thứ ~i~ cho phép truyền tin từ máy ~u_{i}~ đến máy ~v_{i}~, ~i = 1~, ~2~, ..., ~m~.
Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.
Output
- Dòng đầu tiên ghi 'YES' nếu câu trả lời là khẳng định, ghi 'NO' nếu câu trả lời là phủ định.
- Nếu câu trả lời là khẳng định thì dòng thứ hai ghi hai số nguyên dương ~u~, ~v~ cách nhau bởi dấu cách cho biết cần bổ sung kênh truyền tin từ máy ~u~ đến máy ~v~ để biến mạng thành thông suốt.
Giới hạn
Trong tất cả các test, ~n \leq 2000~, ~m \leq 30000~.
Sample Input
3 2
1 2
2 3
Sample Output
YES
3 1
Comments
Mình có thắc mắc như thế này, mong mng giải thích: Ở test case sau:
3 2
1 2
3 2
thì đồ thị là thoả mãn tính chất "hầu như thông suốt" của đề bài. Nhưng rõ ràng không thể chỉ thêm đúng 1 cạnh để biến đồ thị thành "thông suốt".
Mình có mạn phép copy code từ Editorial để chạy thử test này thì vẫn ra YES.
Xin cảm ơn mọi người!
test này đâu có hầu như thông suốt đâu bn vì k có đường nào từ 1 đến 3 hay từ 3 đến 1
This comment is hidden due to too much negative feedback. Show it anyway.
Code mẫu đã AC rồi nha!
This comment is hidden due to too much negative feedback. Show it anyway.
Bài này greedy được đó
This comment is hidden due to too much negative feedback. Show it anyway.