Phân công điều kiện 2-SAT

General
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Có $N$ biến boolean $x_1, x_2, \dots, x_N$ và $M$ mệnh đề ràng buộc. Mỗi mệnh đề có dạng $(a \lor b)$, trong đó $a, b$ là các số nguyên khác $0$ có trị tuyệt đối từ $1$ đến $N$: số dương $k$ biểu diễn $x_k$ đúng, còn số âm $-k$ biểu diễn $\neg x_k$ ($x_k$ sai).

Hãy kiểm tra xem có tồn tại phép gán giá trị đúng/sai cho $N$ biến sao cho tất cả $M$ mệnh đề đều đúng hay không.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên khác $0$ là $a, b$ ($1 \le |a|, |b| \le N$).
Dữ liệu ra

In ra YES nếu tồn tại phép gán thỏa mãn, ngược lại in ra NO.

Ví dụ
Input Output
2 3
1 2
-1 2
1 -2
YES
1 2
1 1
-1 -1
NO
Giới hạn

$1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$.

Draft saved