题目描述
有 n 个布尔变量 x1∼xn。给定 m 个形如 (xa=va)∨(xb=vb) 的条件(v∈{0,1}),判断是否存在一组赋值使所有条件都成立;若存在输出 YES,否则输出 NO。
题目类型
2-SAT、强连通分量
输入格式
第一行两个整数 n,m。
接下来 m 行,每行四个整数 a,va,b,vb。
输出格式
一行 YES 或 NO。
样例 #1
样例输入 #1
2 2
1 1 2 1
1 0 2 0
样例输出 #1
YES
数据规模与约定
| 数据范围 |
说明 |
| 1≤n≤5×103 |
变量数 |
| 1≤m≤2×104 |
条件数 |
- 每个变量拆成两个点,连边 (xa=va)→(xb=vb) 与 (xb=vb)→(xa=va);若某变量的两个点在同一 SCC 内则无解。