VOI 06 Bài 5 - Mạng máy tính
Xem dạng 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
Bình luận
Test yếu quá
:vv
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Hình như test case của bạn không đúng yêu cầu bài toán: "mạng máy tính đã cho là hầu như thông suốt nhưng không thông suốt" vì cặp (1,3), (3,1) không tồn tại đường đi, nên câu hỏi của bạn sai từ lúc đầu rồi :v
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
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Code mẫu đã AC rồi nha!
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.