Phân công điều kiện 2-SAT
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề 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$.
Community Discussion