Vương Quốc Thống Nhất

Buổi 43 — SCC (Tarjan) & 2-SAT
Points
18
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Vương quốc có N thành phố và M con đường một chiều. Hãy kiểm tra xem đồ thị có phải là liên thông mạnh hay không, tức là từ bất kỳ thành phố nào cũng có thể đi đến mọi thành phố khác.

In "YES" nếu đồ thị liên thông mạnh, ngược lại in "NO".

Dữ liệu vào
  • Dòng đầu: hai số nguyên N và M (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000)
  • M dòng tiếp theo, mỗi dòng chứa hai số nguyên u v (1 ≤ u, v ≤ N)
Dữ liệu ra
  • In "YES" hoặc "NO".
Ví dụ
Input Output
3 3\n1 2\n2 3\n3 1 YES
3 2\n1 2\n2 3 NO
Giới hạn
  • 1 ≤ N ≤ 100000
  • 0 ≤ M ≤ 200000
Draft saved