Xây đường

View as PDF

Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Một quốc gia nọ có N thành phố. Người ta đã xây dựng M con đường một chiều để di chuyển giữa các thành phố. Quốc vương muốn đảm bảo rằng giữa hai thành phố bất kỳ, phải luôn tồn tại một cách di chuyển (trực tiếp hoặc gián tiếp) từ thành phố này đến thành phố kia. Bạn hãy kiểm tra xem ông có cần phải xây dựng các con đường mới không?

Dữ liệu vào:

  • Dòng một chứa số nguyên dương T (T5) là số lượng quốc gia bạn cần giúp đỡ.
  • Tiếp theo là T bộ dữ liệu, mỗi bộ dữ liệu gồm:
  • Dòng đầu chứa 2 số nguyên N,M, số thành phố và số con đường 1 chiều
  • Mỗi dòng trong M dòng tiếp theo gồm 2 số nguyên u,v (1u,vn, uv): người ta đã xây dựng con đường 1 chiều từ u đến v.

Dữ liệu ra:

Mỗi dòng là câu trả lời cho một bộ dữ liệu tương ứng: in ra YES nếu quốc vương cần xây thêm đường mới, NO nếu những con đường hiện tại đã thỏa mãn yêu cầu của ông.

Ví dụ:
Input:
Copy
2
3 3
1 2
2 3
3 1
3 2
1 2
2 3
Output:
Copy
NO
YES

Ràng buộc:

  • 40% điểm tương ứng với trường hợp N,M2000.
  • 60% điểm tương ứng với trường hợp N,M100000.

Giải thích:

Trong bộ dữ liệu thứ hai, có 2 con đường 1223. Người ta không thể di chuyển từ thành phố 3 đến thành phố 1 với hai con đường này.


Comments

Please read the guidelines before commenting.



  • -1
    anhtuan2007  commented 4:36:14 pm, 24/08/2022

    Amelia Watson is my life