Skip to main content

洛谷 P4782 【模板】2-SAT

nn 个布尔变量 x1xnx_1\sim x_n,另有 mm 个需要满足的条件,每个条件的形式都是「xix_itrue / falsexjx_jtrue / false」。例如「x1x_1 为真或 x3x_3 为假」、「x7x_7 为假或 x2x_2 为假」。

2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。