Hai Phe Đối Lập

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

Có N người và M mối quan hệ. Mỗi mối quan hệ có dạng: "người a và người b không thể ở cùng một phe". Hãy kiểm tra xem có thể chia N người thành 2 phe sao cho thỏa mãn tất cả các ràng buộc hay không.

Đây là bài toán 2-SAT cơ bản: với mỗi ràng buộc (a, b), ta có xa ⊕ xb = 1 (a và b phải khác phe), tương đương (xa → ¬xb) ∧ (xb → ¬xa) ∧ (¬xa → xb) ∧ (¬xb → xa).

In "YES" nếu tồn tại cách chia, 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: a b (1 ≤ a, b ≤ N)
Dữ liệu ra
  • "YES" hoặc "NO"
Ví dụ
Input Output
4 4\n1 2\n2 3\n3 4\n4 1 YES
3 3\n1 2\n2 3\n1 3 NO
Giới hạn
  • 1 ≤ N ≤ 100000
  • 0 ≤ M ≤ 200000
Draft saved