VOI 06 Bài 5 - Mạng máy tính

View as PDF
Submit solution
Points: 0.21 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
Ðề thi quốc gia 2006
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Mộ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

Please read the guidelines before commenting.


  • 1
    DAThinh_HuMaDa  commented on Feb. 1, 2026, 2:38 p.m. ← edit 5

    dùng tarjan để tìm TPLT

    xét nếu đồ thị chỉ có 1 TPLT in ra "NO" và kết thúc chương trình

    nếu có hơn 1 thành phần liên thông ta in ra "YES" sau đó lấy một điểm của TPLT đầu và một điểm của liên thông cuối

    đây sẽ là 1 điểm bất kỳ trong TPLT đầu và cuối tốt nhất nên dùng phần tử đầu tiên của TPLT đầu và cuối


  • -1
    vidueduo  commented on April 14, 2025, 2:56 p.m.

    Test yếu quá


  • -5
    minzdapoet1102  commented on Sept. 11, 2024, 1:03 p.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -1
      Groot  commented on July 21, 2025, 9:10 p.m.

      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


    • 4
      thanhAOC123  commented on Sept. 17, 2024, 3:11 a.m.

      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


    • -9
      monaxia  commented on Sept. 11, 2024, 1:47 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


      • 1
        minzdapoet1102  commented on Sept. 12, 2024, 4:31 p.m.

        Code mẫu đã AC rồi nha!


  • -20
    chunguyen2k8  commented on July 21, 2024, 3:44 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -6
    khanhphamlc  commented on Dec. 4, 2023, 11:18 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -37
    PhanTienDung  commented on Aug. 6, 2022, 9:11 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.