#O1053. 2-SAT

2-SAT

题目描述

有 nn 个布尔变量 x1∼xnx_1 \sim x_n。给定 mm 个形如 (xa=va)∨(xb=vb)(x_a = v_a) \lor (x_b = v_b) 的条件(v∈{0,1}v \in \{0,1\}),判断是否存在一组赋值使所有条件都成立;若存在输出 YES,否则输出 NO。

题目类型

2-SAT、强连通分量

输入格式

第一行两个整数 n,mn, m。

接下来 mm 行,每行四个整数 a,va,b,vba, v_a, b, v_b。

输出格式

一行 YES 或 NO。

样例 #1

样例输入 #1

2 2
1 1 2 1
1 0 2 0

样例输出 #1

YES

数据规模与约定

数据范围 说明
1≤n≤5×1031 \le n \le 5 \times 10^3 变量数
1≤m≤2×1041 \le m \le 2 \times 10^4 条件数
  • 每个变量拆成两个点,连边 (xa≠va)→(xb=vb)(x_a \ne v_a) \to (x_b = v_b) 与 (xb≠vb)→(xa=va)(x_b \ne v_b) \to (x_a = v_a);若某变量的两个点在同一 SCC 内则无解。